Problem Statement

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

A connected component is a maximal set of nodes such that each pair of nodes is connected by a path, and no node outside the set is connected to any node in the set.

Additional information

• 1 <= n <= 2000
• 1 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= ai <= bi < n
• ai != bi
• There are no repeated edges.

Example 1:

Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]

Output: 2

Explanation: Nodes 0, 1, and 2 form one connected component. Nodes 3 and 4 form a second connected component.

Example 2:

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

Output: 1

Explanation: All nodes are connected in a single path, forming exactly 1 component.

Standard Traversal (Depth-First Search)

Intuition

The most straightforward way to count connected components is to systematically explore the graph. We can iterate through every single node from 0 to n - 1.

If we find a node that we haven't visited yet, it must be the start of a brand new, undiscovered component! We increment our component counter by 1. Then, we immediately launch a Depth-First Search (DFS) from that node. The DFS will travel across all connected edges, marking every single node in that specific cluster as visited.

When the DFS finishes and the main loop continues, it will skip over all those freshly visited nodes, ensuring we never double-count a component.

Algorithm

1. Initialize an empty adjacency list adj using a dictionary.
2. Iterate through edges and populate the adjacency list. Since the graph is undirected, for every edge [u, v], append v to adj[u] and u to adj[v].
3. Initialize a visited set and a components counter set to 0.
4. Define a recursive helper function dfs(node):

• Add node to visited.
• Loop through all neighbors of node in adj.
• If a neighbor is not in visited, recursively call dfs(neighbor).

5. Iterate i from 0 to n - 1.
6. If i is not in visited, we found a new component:

• Increment components by 1.
• Call dfs(i) to map out and mark the rest of the component.

7. Return components.

def count_components(n: int, edges: list[list[int]]) -> int:
    # Build the adjacency list
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
        
    visited = set()
    components = 0
    
    def dfs(node):
        visited.add(node)
        for neighbor in adj[node]:
            if neighbor not in visited:
                dfs(neighbor)
                
    # Iterate through every node
    for i in range(n):
        if i not in visited:
            components += 1
            dfs(i)
            
    return components

Time & Space Complexity

• Time complexity: O(V + E)

• Reason: We iterate through all Vertices (n) and Edges to build the adjacency list. During the DFS, each node is visited exactly once, and each edge is traversed twice (once from each direction).

• Space complexity: O(V + E)

• Reason: The adjacency list takes O(V + E) space to store all connections. The visited set and the recursion stack take up to O(V) space.

Union-Find (Disjoint Set) - Optimal Space

Intuition

We can solve this dynamically and with less memory overhead using the Union-Find algorithm.

Imagine we start with n completely isolated nodes. At this point, we have exactly n connected components.
As we iterate through the given edges, we attempt to connect (Union) the two nodes. If the two nodes were previously in separate components (they have different "roots"), merging them naturally reduces our total component count by exactly 1!

If the two nodes already share the same root, they are already part of the same component, so the total count doesn't change. By the time we process all edges, our remaining count is the exact number of isolated components.

Algorithm

1. Initialize a parent array of size n where parent[i] = i (each node is its own root).
2. Initialize a rank array of size n with all 1s (to keep trees balanced).
3. Define the find(node) function with Path Compression:

• Traverse up the parent pointers until p == parent[p].
• Compress the path by pointing nodes directly to their grandparent.

4. Define the union(n1, n2) function:

• Find the roots p1 and p2.
• If p1 == p2, they are already connected. Return 0.
• Otherwise, attach the smaller rank tree to the larger rank tree. Return 1 (indicating a successful merge).

5. Initialize components = n.
6. Iterate through each u, v in edges.
7. Subtract the result of union(u, v) from components. (If they merge, components decreases by 1. If they were already connected, it subtracts 0).
8. Return components.

def count_components(n: int, edges: list[list[int]]) -> int:
    parent = [i for i in range(n)]
    rank = [1] * n
    
    def find(node):
        p = parent[node]
        while p != parent[p]:
            # Path compression
            parent[p] = parent[parent[p]]
            p = parent[p]
        return p
        
    def union(n1, n2):
        p1, p2 = find(n1), find(n2)
        
        # Already in the same component
        if p1 == p2:
            return 0
            
        # Merge components by rank
        if rank[p1] > rank[p2]:
            parent[p2] = p1
            rank[p1] += rank[p2]
        else:
            parent[p1] = p2
            rank[p2] += rank[p1]
            
        return 1
        
    components = n
    for u, v in edges:
        components -= union(u, v)
        
    return components

Time & Space Complexity

• Time complexity: O(V + E)

• Reason: Processing each of the E edges takes amortized O(1) time due to Path Compression and Union by Rank. Thus, the time is strictly bounded by the number of nodes (V) to initialize the arrays, plus the number of edges (E) processed. Mathematically O(V + E * α(V)).

• Space complexity: O(V)

• Reason: We completely avoid building an O(V + E) adjacency list. The parent and rank arrays take exactly O(V) space.