Number of Connected Components in an Undirected Graph medium

Problem Statement

You have been given an integer n representing the number of nodes in an undirected graph. You are also given an array edges where edges[i] = [u, v] indicates that there is an undirected edge between nodes u and v. Your task is to 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: [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, and a count variable to store the number of connected components.

2. Depth-First Search (DFS): Implement a DFS function to explore all nodes reachable from a starting node. Mark visited nodes as true in the visited array.

3. Iteration: Iterate through all nodes in the graph. If a node hasn't been visited, increment the count (a new connected component found) and perform DFS starting from that node.

4. Return: Return the final count.

Explanation

The algorithm uses Depth-First Search (DFS) to traverse the graph. DFS systematically explores all reachable nodes from a starting node. By iterating through all nodes and performing DFS only on unvisited nodes, we ensure that each connected component is counted exactly once. The visited array is crucial for preventing cycles and ensuring that each node is visited only once within a connected component.

Code

#include <vector>

using namespace std;

class Solution {
public:
    void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
        visited[node] = true;
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, adj, visited);
            }
        }
    }

    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n); // Adjacency list
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]); // Undirected graph
        }

        vector<bool> visited(n, false); // Track visited nodes
        int count = 0; // Number of connected components

        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                dfs(i, adj, visited);
                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 DFS visits each node and edge at most once.

• Space Complexity: O(V), due to the adjacency list and the visited array. The recursive call stack in DFS can also take up to O(V) space in the worst case (a very deep graph).