Published: Sep 17, 2022
This is a typical graph traversal problem. Either of depth-first search or breadth-first search works.
ncities. Some of them are connected, while some are not. If city
ais connected directly with city
b, and city
bis connected directly with city
c, then city
ais 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 nmatrix isConnected where
isConnected[i][j] = 1if the ith city and the j-th city are directly connected, and
isConnected[i][j] = 0otherwise.
Return the total number of provinces.
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]
Example 1 Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2
Example 2 Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]] Output: 3
In this problem, the adjacency matrix is already given. We don’t need to construct it. Staring from 0, which means row 0, going over all nodes one by one while keeping a visited set. When the current row’s column value is 1, two nodes are connected. If it is not yet visited, add the node to queue for further connectivity check. When one round of BFS ends, a province is found, so count up.
class NumberOfProvinces: def findCircleNum(self, isConnected: List[List[int]]) -> int: n = len(isConnected) count, visited = 0, set() for i in range(n): if i in visited: continue queue = [i] count += 1 while queue: cur = queue.pop(0) visited.add(cur) for j in range(n): if isConnected[cur][j] == 1 and j not in visited: queue.append(j) return count