Number of Provinces - LeetCode
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
- code
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
visited = [False] * n
def dfs(city):
visited[city] = True
for nei, connected in enumerate(isConnected[city]):
if connected == 1 and not visited[nei]:
dfs(nei)
province = 0
for i in range(n):
if not visited[i]:
dfs(i)
province += 1
return province
- code
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
self.isolated = n = len(isConnected)
root = list(range(n))
rank = [1] * n
def find(i):
if i != root[i]:
root[i] = find(root[i])
return root[i]
def union(i, j):
rti = find(i)
rtj = find(j)
if rti != rtj:
if rank[rti] > rank[rtj]:
root[rtj] = rti
elif rank[rti] < rank[rtj]:
root[rti] = rtj
else:
root[rti] = rtj
rank[rtj] += 1
self.isolated -= 1 # a merge made
for i in range(n):
for j in range(i+1, n):
if isConnected[i][j]:
union(i, j)
return self.isolated