Union-Find. Count distinct components.
class UnionFind: def init(self, n): self.parent = list(range(n)) def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): px, py = self.find(x), self.find(y) if px != py: self.parent[px] = py
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 sum(1 for i in range(n) if uf.find(i) == i)
time, space.