Medium
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
Constraints:
1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]is1or0.isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
class City:
def __init__(self, size):
self.root = [i for i in range(size)]
self.rank = [1]*size
def find(self, x):
if self.root[x] == x:
return x
else:
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x,y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.root[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.root[rootX] = rootY
else:
self.root[rootY] = rootX
self.rank[rootX]+=1
def isConected(self, x,y):
return self.root[x] == self.root[y]
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
city_count = len(isConnected)
uf = City(city_count)
for index, city in enumerate(isConnected):
for i, link in enumerate(city):
if i!=index:
if link!=0:
uf.union(index, i)
p = set()
for city in range(city_count):
p.add(uf.find(city))
return(len(p))