# Number of Provinces

2 min readFeb 17, 2021

--

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.

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`

DFS深度搜索，遇见一个没有见过的，mark as visited。

Solution

`def findCircleNum(self, isConnected): “”” :type isConnected: List[List[int]] :rtype: int “”” “”” DFS the matrix, whenever we run into to a 1, run DFS and clear that island with ans + 1 “”” ans = 0 rowLen = len(isConnected)  visited = [False]*rowLen def dfs(i):   visited[i] = True   for j in range(rowLen):     if isConnected[i][j] == 1 and not visited[j]:       dfs(j)  for i in range(rowLen):   if not visited[i]:     dfs(i)     ans += 1  return ans`

iteratively可以用stack来做