Process the adjacency matrix, union connected cities:
function findCircleNum(isConnected):
n = isConnected.length
uf = new UnionFind(n)
for i from 0 to n-1:
for j from i+1 to n-1:
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: .