num-of-connected-components

Number of Connected Components

Approach 1: DFS

adj = [[] for _ in range(n)]
for v, w in edges:
    adj[v].append(w)
    adj[w].append(v)
visited = [False] * n
 
def dfs(v):
    nonlocal adj, visited
    visited[v] = True
    deque((dfs(w) for w in adj[v] if not visited[w]), maxlen=0)
 
counter = 0
for v in range(n):
    if not visited[v]:
        counter += 1
    dfs(v)
return counter

Approach 2: Union Find

class UnionFind(list):
    def __init__(self, n):
        super().__init__(range(n))
        self.count = n
 
    def __getitem__(self, v):
        while True:
            p = super().__getitem__(v)
            if p == v:
                break
            v = p
        return p
 
    def union(self, u, v):
        if not self[u] == self[v]:
            self[self[u]] = self[v]
            self.count -= 1
 
unionFind = UnionFind(n)
for u, v in edges:
    unionFind.union(u, v)
return unionFind.count