Number of Connected Components in an Undirected Graph medium

Problem Statement

You have been given an undirected graph represented as an adjacency list n nodes where each node has a label from 0 to n - 1. The graph is represented by a 2D integer array edges where edges[i] = [u, v] indicates that there is an undirected edge between nodes u and v. You are also given an integer n. Find the number of connected components in the graph.

Example 1

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

Output: 2

Explanation: There are two connected components in the graph: {0, 1, 2} and {3, 4}.

Example 2

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

Output: 1

Explanation: There is only one connected component in the graph: {0, 1, 2, 3, 4}.

Steps

1. Initialization: Create an adjacency list to represent the graph. Create a visited array to keep track of visited nodes during Depth-First Search (DFS). Initialize the count of connected components to 0.

2. Depth-First Search (DFS): Iterate through each node. If a node is not visited, perform DFS starting from that node. The DFS traversal will mark all nodes reachable from the starting node as visited. Increment the connected component count after each DFS traversal.

3. Return Count: After iterating through all nodes, return the count of connected components.

Explanation

The algorithm uses Depth-First Search (DFS) to explore the graph. DFS is suitable for finding connected components because it systematically explores all reachable nodes from a starting point. By iterating through all nodes and performing DFS only on unvisited nodes, we ensure that each connected component is counted exactly once.

Code

function countComponents(n: number, edges: number[][]): number {
    // Create adjacency list
    const adjList: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        adjList[u].push(v);
        adjList[v].push(u);
    }

    // Visited array
    const visited: boolean[] = new Array(n).fill(false);

    // DFS function
    const dfs = (node: number) => {
        visited[node] = true;
        for (const neighbor of adjList[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    };

    // Count connected components
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            count++;
        }
    }

    return count;
};

Complexity

• Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is because we visit each vertex and edge at most once during the DFS traversals.

• Space Complexity: O(V), where V is the number of vertices. This is due to the space used by the visited array and the recursion stack in the DFS function. The adjacency list also takes O(V+E) space, but in the worst case, E could be V^2 making O(V) a more precise representation of the space complexity if we ignore the adjacency list's space.