Connected Components — Union-Find / BFS

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        parent=list(range(n)); count=n
        def find(x):
            while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
            return x
        for u,v in edges:
            pu,pv=find(u),find(v)
            if pu!=pv: parent[pu]=pv; count-=1
        return count

from collections import deque, defaultdict
class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        adj=defaultdict(list)
        for u,v in edges: adj[u].append(v); adj[v].append(u)
        visited=set(); count=0
        for i in range(n):
            if i not in visited:
                count+=1; q=deque([i]); visited.add(i)
                while q:
                    node=q.popleft()
                    for nb in adj[node]:
                        if nb not in visited: visited.add(nb); q.append(nb)
        return count