Back to Problems

Number of Provinces

Medium
Union Find

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Union Find Approach:

  • Each city starts as its own set
  • For each connection (i, j), perform union(i, j)
  • Count the number of distinct roots (connected components)

Key Insight: The number of provinces equals the number of disjoint sets after processing all connections.

Example 1

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Explanation: Cities 0 and 1 are connected (same province). City 2 is its own province. Total: 2 provinces.

Example 2

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: No cities are connected. Each city is its own province. Total: 3 provinces.

Example 3

Input: isConnected = [[1,1,1],[1,1,1],[1,1,1]]
Output: 1
Explanation: All cities are connected (directly or indirectly). Total: 1 province.

Constraints

  • •1 <= n <= 200
  • •n == isConnected.length
  • •n == isConnected[i].length
  • •isConnected[i][j] is 1 or 0
  • •isConnected[i][i] == 1
  • •isConnected[i][j] == isConnected[j][i]
Show Hints (4)
Hint 1: What does each element in the matrix represent? How does a connection between cities i and j affect which province they belong to?
Hint 2: When you see "connected components" in a graph, what data structures come to mind? Union Find is perfect for tracking which elements belong to the same group.
Hint 3: After processing all connections, how would you count the number of unique provinces? Think about what makes an element a "root" in Union Find.
Hint 4: Remember to only process each connection once. Since the matrix is symmetric, you only need to look at either the upper or lower triangle.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?