Devin's Blog

Number of Connected Components in an Undirected Graph

2 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

  • This problem is Union Find as a problem.
  • Use Union Find, noticing that every time you union, you get one less connected component.

Code

Union Find

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # Initialize each node to be a parent of itself
        parent = [i for i in range(n)]
 
        def union(x, y):
            # If they both have the same parent, do not need to union them
            if find(x) == find(y):
                return False
            
            # Update the root parent of x to be y
            parent[find(x)] = y
            return True
 
        def find(x):
            # If not at root element
            if x != parent[x]:
                # Set parent of x to the godfather (by recursively calling until a node is the parent of itself)
                parent[x] = find(parent[x])
                return parent[x]
 
            # Return root element
            return x
 
        connected_components = n
        for u, v in edges:
            # By unioning two sub-groups together, you get one less connected component (since you started at each component being connected)
            if union(u, v):
                connected_components -= 1
        
        return connected_components

DFS

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()
 
        @cache
        def dfs(node):
            if node in visited:
                return
            
            visited.add(node)
            for u in adj[node]:
                dfs(u)
        
        count = 0
        for i in range(n):
            if i not in visited:
                count += 1
                dfs(i)
        return count

Notes

Cards

START Basic Front: Number of Connected Components in an Undirected Graph Back: Use Union Find, noticing that every time you union, you get one less connected component.

END

References

Graph View