0547 Number of Provinces

0547 Number of Provinces#

Problem#

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.

Examples#

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

Constraint#

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]

Analysis#

It is really easy to mix this problem with problem that calculates the number of islands (see 0200).

When using the flood algorithm, we need not only flood the directely connected nodes, but also flood the indirect connected nodes.

def findCircleNum(isConnected):
    n = len(isConnected)
    visited = [False] * n

    def dfs(isConnected, visited, i):
        for j in range(len(isConnected)):
            if isConnected[i][j] == 1 and not visited[j]:
                visited[j] = True
                dfs(isConnected, visited, j)
    
    count = 0
    for i in range(n):
        if not visited[i]:
            dfs(isConnected, visited, i)
            count += 1
    return count

# test
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
print(findCircleNum(isConnected))

isConnected = [[1,0,0],[0,1,0],[0,0,1]]
print(findCircleNum(isConnected))

2
3
Contents