547. Number of Provinces
class UnionFind:
def __init__(self, size):
self.root = [i for i in range(size)]
self.rank = [1] * size
self.count = size
def find(self, x):
if x == self.root[x]:
return x
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
self.count -= 1
def getCount(self):
return self.count
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
if not isConnected or len(isConnected) == 0:
return 0
n = len(isConnected)
uf = UnionFind(n)
for i in range(n):
for j in range(n):
if isConnected[i][j] == 1:
uf.union(i, j)
return uf.getCount()