Process the adjacency matrix, union connected cities:
def findCircleNum(isConnected):
n = len(isConnected)
uf = UnionFind(n)
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
uf.union(i, j)
return uf.count
Only check since the matrix is symmetric—this avoids processing each edge twice.
Alternative: DFS from each unvisited node, counting the number of DFS starts. Both approaches work; Union-Find is cleaner here.
Time: . Space: .