Number of Connected Components in an Undirected Graph medium

Problem Statement

You have been given an undirected graph represented as an integer array n where n[i] is the number of nodes. You are also given an array of edges where each edge is a pair of nodes [u, v]. The task is to find the number of connected components in the graph. A connected component is a subgraph where every node is reachable from every other node in the subgraph.

Example 1

Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2 Explanation: There are two connected components: {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: {0,1,2,3,4}.

Steps

1. Initialization: Create an adjacency list to represent the graph. Initialize a visited array to track visited nodes. Set the number of connected components (count) to 0.

2. Depth-First Search (DFS): Iterate through all nodes. If a node hasn't been visited, perform a DFS starting from that node. The DFS will mark all reachable nodes as visited. Each time a DFS is initiated (meaning a new connected component is found), increment count.

3. Return: After iterating through all nodes, return count.

Explanation

The algorithm uses Depth-First Search (DFS) to explore the graph. DFS systematically visits all nodes reachable from a starting node. By iterating through all nodes and starting a DFS only when encountering an unvisited node, we effectively identify and count each connected component. Each call to DFS explores one connected component.

Code

import java.util.*;

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]); // Undirected graph
        }

        boolean[] visited = new boolean[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(adjList, visited, i);
                count++;
            }
        }

        return count;
    }

    private void dfs(List<List<Integer>> adjList, boolean[] visited, int node) {
        visited[node] = true;
        for (int neighbor : adjList.get(node)) {
            if (!visited[neighbor]) {
                dfs(adjList, visited, neighbor);
            }
        }
    }
}

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 node and edge at most once during the DFS traversal.

• Space Complexity: O(V) in the worst case. This is due to the space used by the visited array and the recursion stack during the DFS (which can be as deep as the height of the graph). The adjacency list also uses O(V+E) space, but this is dominated by the O(V) space used by the visited array in the worst case (a graph with many isolated nodes would have a large V compared to E).