Number of Connected Components in an Undirected Graph medium

Problem Statement

You have been given an undirected graph represented as an integer array n and an array of edges edges. The number of nodes in the graph is n. edges[i] = [u<sub>i</sub>, v<sub>i</sub>] indicates that there is an undirected edge between nodes u<sub>i</sub> and v<sub>i</sub>.

You are required to find the number of connected components in the given graph. A connected component is a subset of the graph where any two nodes are connected by a path.

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. The count of connected components starts at 0.

2. Depth-First Search (DFS): Iterate through each node. If a node hasn't been visited, perform a DFS starting from that node. The DFS explores all reachable nodes from the starting node, marking them as visited. Each time a DFS is initiated from an unvisited node, it indicates a new connected component.

3. Counting Components: Increment the count of connected components after each DFS traversal.

4. Return: Return the final count of connected components.

Explanation

The algorithm uses Depth-First Search (DFS) to traverse the graph. DFS efficiently explores all nodes connected to a starting node. By iterating through all nodes and initiating a DFS only when an unvisited node is encountered, we ensure that each connected component is counted exactly once. The visited array prevents revisiting nodes and ensures the correct exploration of the graph.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int CountComponents(int n, int[][] edges) {
        // Create adjacency list
        List<int>[] adj = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
        }
        foreach (int[] edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]); // Undirected graph
        }

        // Initialize visited array
        bool[] visited = new bool[n];

        // Count connected components
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                DFS(adj, visited, i);
                count++;
            }
        }

        return count;
    }

    // Depth-First Search
    private void DFS(List<int>[] adj, bool[] visited, int u) {
        visited[u] = true;
        foreach (int v in adj[u]) {
            if (!visited[v]) {
                DFS(adj, visited, v);
            }
        }
    }
}

Complexity

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

• Space Complexity: O(V), primarily due to the visited array and the recursion stack in the DFS. The adjacency list also takes O(V+E) space but this is often considered within the same order as the number of vertices and edges, especially for sparse graphs.