Problem Description

The "Number of Connected Components in an Undirected Graph" problem asks you to determine how many connected components exist in a given undirected graph. The graph is described by:

• An integer n representing the number of nodes, labeled from 0 to n-1.
• A list of undirected edges, where each edge is a pair [u, v] connecting node u and node v.

A connected component is a set of nodes such that there is a path between every pair of nodes in the set, and no node in the set is connected to any node outside the set.

Your task is to return the total number of connected components in the graph. Each edge can be used only once, and the same node cannot be counted in multiple components.

Thought Process

To solve this problem, let's first understand what a connected component is: it's a group of nodes where every node is reachable from every other node in the same group, and there are no connections to nodes outside the group.

The brute-force approach would be to try to visit every possible combination of nodes and check if they're connected, but this is very inefficient, especially for large graphs.

Instead, we can use classic graph traversal techniques like Depth-First Search (DFS) or Breadth-First Search (BFS). The idea is to start from an unvisited node, perform a traversal marking all reachable nodes as visited, and then repeat the process from the next unvisited node. Each traversal corresponds to one connected component.

Another efficient approach is the Union-Find (Disjoint Set Union, DSU) data structure, which helps to quickly group nodes into components and count the number of unique groups.

Solution Approach

We can solve the problem using either DFS/BFS or Union-Find. Let's break down the DFS/BFS approach, as it's conceptually easier for beginners:

1. Build the Graph: Represent the graph using an adjacency list. This makes it easy to look up all neighbors of a node.
2. Track Visited Nodes: Use a set or boolean array to keep track of which nodes have already been visited.
3. Count Components: Loop through all nodes. For each unvisited node, perform a DFS or BFS starting from that node, marking all reachable nodes as visited. Each time you start a new traversal, increment your component count.

Why this works: Each traversal marks all nodes in a single connected component as visited. By counting the number of traversals needed to visit all nodes, you count the number of connected components.

Union-Find: Alternatively, Union-Find efficiently merges nodes into groups as edges are processed. At the end, the number of unique group leaders (roots) gives the number of connected components.

Example Walkthrough

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

• Step 1: Build adjacency list
  0: [1]
1: [0,2]
2: [1]
3: [4]
4: [3]
• Step 2: Initialize visited set
  visited = {}
• Step 3: Loop through nodes 0 to 4
  • Node 0 not visited: start DFS/BFS from 0, visit 0,1,2. Mark as visited.
    Component count = 1.
  • Node 1 already visited.
  • Node 2 already visited.
  • Node 3 not visited: start DFS/BFS from 3, visit 3,4. Mark as visited.
    Component count = 2.
  • Node 4 already visited.
• Step 4: All nodes visited. Return component count = 2.

Time and Space Complexity

Brute-force: Checking all possible subsets or paths is exponential and not feasible for large n.

Optimized (DFS/BFS):

• Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. Each node and edge is visited once.
• Space Complexity: O(n + m) for the adjacency list and visited set/array.

Summary

The key to this problem is recognizing that each traversal from an unvisited node finds a new connected component. By using DFS, BFS, or Union-Find, we efficiently group nodes and count the number of components. The approach is elegant because it leverages fundamental graph traversal techniques and data structures to achieve linear time complexity.

Code Implementation

class Solution:
    def countComponents(self, n, edges):
        from collections import defaultdict, deque

        adj = defaultdict(list)
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        visited = set()
        count = 0

        def dfs(node):
            stack = [node]
            while stack:
                curr = stack.pop()
                if curr not in visited:
                    visited.add(curr)
                    for neighbor in adj[curr]:
                        if neighbor not in visited:
                            stack.append(neighbor)

        for i in range(n):
            if i not in visited:
                dfs(i)
                count += 1
        return count
      

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        vector<bool> visited(n, false);
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                dfs(i, adj, visited);
                ++count;
            }
        }
        return count;
    }
private:
    void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
        stack<int> stk;
        stk.push(node);
        while (!stk.empty()) {
            int curr = stk.top(); stk.pop();
            if (!visited[curr]) {
                visited[curr] = true;
                for (int neighbor : adj[curr]) {
                    if (!visited[neighbor]) {
                        stk.push(neighbor);
                    }
                }
            }
        }
    }
};
      

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited);
                count++;
            }
        }
        return count;
    }
    private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        Stack<Integer> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            int curr = stack.pop();
            if (!visited[curr]) {
                visited[curr] = true;
                for (int neighbor : adj.get(curr)) {
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
}
      

var countComponents = function(n, edges) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const visited = new Set();
    let count = 0;

    function dfs(node) {
        const stack = [node];
        while (stack.length) {
            const curr = stack.pop();
            if (!visited.has(curr)) {
                visited.add(curr);
                for (const neighbor of adj[curr]) {
                    if (!visited.has(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            dfs(i);
            count++;
        }
    }
    return count;
};