Solutions

# DFS, BFS, or DSU to count the number of connected components in an undirected graph.
# graphs

# DFS - O(E+V) time, O(E+V) space
def countComponents1(n: int, edges: list[list[int]]) -> int:
    adj = {i: [] for i in range(n)}
    for u,v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = set()

    def dfs(u: int, parent: int):
        if u in visited:
            return
        
        visited.add(u)
        for n in adj[u]:
            if n == parent:
                continue
            dfs(n, u)


    components = 0
    for n in range(n):
        if n not in visited:
            dfs(n, -1)
            components += 1

    return components
        

# BFS - O(E+V) time, O(E+V) space
def countComponents(n: int, edges: list[list[int]]) -> int:
    adj = {i: [] for i in range(n)}
    for u,v in edges:
        adj[u].append(v)
        adj[v].append(u)

    from collections import deque

    def bfs(node: int):
        q = deque()
        q.append(node)
        visited.add(node)
        while q:
            v = q.popleft()
            if v not in adj:
                continue
            for nei in adj[v]:
                if nei not in visited:
                    visited.add(nei)
                    q.append(nei)

    visited = set()
    components = 0
    for node in range(n):
        if node not in visited:
            bfs(node)
            components += 1

    return components


# DSU - O(V + alpha E * V) time, O(V) space
def countComponents(n: int, edges: list[list[int]]) -> int:
    dsu = DSU(n)
    components = n

    for u,v in edges:
        if dsu.union(u,v):
            components -= 1

    return components


class DSU:

    def __init__(self, n: int):
        self.parent = [i for i in range(n)]
        self.rank = [1] * n

    def find(self, n: int) -> int:
        if self.parent[n] != n:
            self.parent[n] = self.find(self.parent[n]) # path compression
        return self.parent[n]

    def union(self, u: int, v: int) -> bool:
        pv = self.find(v)
        pu = self.find(u)
        if pv == pu:
            return False
        else:
            if self.rank[pv] > self.rank[pu]:
                pu, pv = pv, pu
            self.parent[pv] = pu
            self.rank[pu] += self.rank[pv]
            return True