There are n cities. isConnected[i][j] = 1 means cities i and j are directly connected, and 0 means they are not. Connection is transitive: if a connects to b and b connects to c, then a and c are in the same group. A province is a group of cities connected directly or indirectly, with no other city outside the group. Return the number of provinces.
- 1 <= n <= 200
- isConnected[i][j] is 0 or 1
- isConnected[i][i] = 1
- isConnected[i][j] = isConnected[j][i]
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Each city is a node and each 1 in the matrix is an edge, so a province is a connected component. A DFS from every unvisited city works fine. Union Find is another clean way that interviewers like: begin with n groups, and for every connected pair (i, j) merge their groups. Whenever two different groups merge, the count drops by one. With path compression, find is almost O(1), so the matrix scan dominates.
Algorithm
- Create
parent[i] = ifor every city and setcount = n. - Write
find(x)that follows parents to the root, compressing the path on the way. - For every
i < jwithisConnected[i][j] == 1, find both roots. - If the roots differ, link one to the other and decrease
count. - Return
count.
O(n^2 * α(n)), effectively O(n^2)Space: O(n)j > i: the matrix is symmetric and the diagonal is always 1. If asked to go further, add union by rank so the trees stay shallow even without path compression.class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: n = len(isConnected) parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path compression (halving) x = parent[x] return x count = n # every city starts as its own province for i in range(n): for j in range(i + 1, n): if isConnected[i][j] == 1: a, b = find(i), find(j) if a != b: parent[a] = b # merge two provinces count -= 1 return count