#547

Number of Provinces

pupil · 560 · lc medium +28 · verified · 70% accepted · 11,064 likes · top 78%

⚑ DFS / BFS: Connected Components & Reachability ⚑ Disjoint Set Union

Description

There are n cities. A province is a maximal cluster of cities that are all mutually reachable through direct or indirect connections. You are given an n x n adjacency matrix isConnected where isConnected[i][j] = 1 means cities i and j are directly linked, and 0 means they are not. Return the total number of distinct 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

Code

1

2

3

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int: