Problem Statement
You are given an undirected graph consisting of V vertices numbered from 0 to V - 1, and E edges. The ith edge is represented by an array [u, v], denoting a bidirectional edge between vertex u and vertex v.
We say two vertices belong to the same component if there is a valid path from one to the other. A connected component is a maximal subgraph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of it. Your task is to find and return the total number of Connected Components in the graph.
Example 1
Input: V = 4, edges = [[0, 1], [1, 2]]
Output: 2
Explanation: Vertices {0, 1, 2} are linked together and form the first component. Vertex 3 has no edges connected to it, so it stands completely alone and forms the second component.
Example 2
Input: V = 7, edges = [[0, 1], [1, 2], [2, 3], [4, 5]]
Output: 3
Explanation: * The edges [0, 1], [1, 2], [2, 3] form a connected component with vertices {0, 1, 2, 3}.
The edge
[4, 5]forms another connected component with vertices{4, 5}.Vertex
6is completely isolated and forms the third connected component on its own.
Approach 1
A connected component is a group of vertices where every vertex is reachable from the others through one or more edges. A single BFS starting from any vertex can visit every vertex belonging to that component, but it cannot reach vertices that belong to another disconnected component.
To find all connected components, maintain a visited array and scan every vertex from 0 to V - 1. Whenever an unvisited vertex is found, it represents a new connected component. Increment the component count and run BFS from that vertex to visit and mark every vertex belonging to that component.
This process continues until all vertices have been visited, and the final count gives the total number of connected components.
Algorithm
Build an adjacency list for
Vvertices using the givenedges.Initialize a
visitedarray of sizeVwith all values set tofalseand setcount = 0.Traverse every vertex
ifrom0toV - 1and continue when the vertex is already visited.When an unvisited vertex is found, increment
count, mark it visited, and push it into a queue to start BFS.While the queue is not empty, remove the front vertex and visit each of its unvisited neighbors by marking them visited and adding them to the queue.
Continue the outer traversal until every vertex has been processed, then return
countas the total number of connected components.
Dry Run
connected component bfs
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to count the number of connected components using BFS int countComponents(int V, vector<vector<int>>& edges) { // Create an adjacency list to represent the graph vector<vector<int>> adj(V); // Add each edge in both directions since the graph is undirected for (int i = 0; i < edges.size(); i++) { adj[edges[i][0]].push_back(edges[i][1]); adj[edges[i][1]].push_back(edges[i][0]); } // Create a visited array to keep track of visited vertices vector<bool> vis(V, false); // Store the number of connected components int count = 0; // Traverse all vertices to find unvisited components for (int i = 0; i < V; i++) { // Start BFS when an unvisited vertex is found if (!vis[i]) { count++; // Create a queue for BFS traversal queue<int> q; // Add the starting vertex to the queue q.push(i); // Mark the starting vertex as visited vis[i] = true; // Traverse all vertices belonging to the current component while (!q.empty()) { // Get the current vertex from the front of the queue int node = q.front(); q.pop(); // Traverse all adjacent vertices of the current node for (int neighbor : adj[node]) { // Visit the unvisited neighbor and add it to the queue if (!vis[neighbor]) { vis[neighbor] = true; q.push(neighbor); } } } } } return count; }};// Driver code startsint main() { // Create an object of the Solution class Solution sol; // Number of vertices in the graph int V = 7; // Store the edges of the undirected graph vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 3}, {4, 5}}; cout << "Number of Connected Components: " << sol.countComponents(V, edges) << endl; return 0;}Complexity Analysis
Time Complexity: O(V + E). Constructing the adjacency list takes time proportional to the number of edges. The outer loop runs V times, and the inner BFS strictly processes each node and its connected edges exactly once.
Space Complexity: O(V + E). The adjacency list requires O(V + E) space to store the connections. The visited array and the BFS Queue require an additional O(V) auxiliary space.
Approach 2
DFS follows the same connected-component idea as BFS, but instead of using a queue, it explores as deeply as possible through recursion before returning.
A single DFS started from an unvisited vertex visits every vertex reachable from that vertex, covering the complete connected component. After that traversal finishes, any remaining unvisited vertex must belong to a different component. Therefore, we scan all vertices and start a new DFS whenever an unvisited vertex is found.
A visited array ensures that each vertex is processed only once, while the component counter increases exactly when a new component is discovered.
Algorithm
Build an adjacency list for
Vvertices using the givenedges.Initialize a
visitedarray of sizeVwith all values set tofalseand setcount = 0.Traverse every vertex
ifrom0toV - 1and skip it if it has already been visited.When an unvisited vertex is found, increment
countand start a recursive DFS from that vertex.Inside DFS, mark the current vertex as visited and recursively visit every unvisited neighbor.
Continue the outer traversal until all vertices have been processed, then return
countas the total number of connected components.
Dry Run
connected component dfs
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Function to perform DFS traversal from the given node void dfsHelper(int node, vector<vector<int>>& adj, vector<bool>& vis) { // Mark the current node as visited vis[node] = true; // Traverse all adjacent nodes of the current node for (int neighbor : adj[node]) { // Visit the unvisited neighbor using DFS if (!vis[neighbor]) { dfsHelper(neighbor, adj, vis); } } }public: // Function to count the number of connected components using DFS int countComponents(int V, vector<vector<int>>& edges) { // Create an adjacency list to represent the graph vector<vector<int>> adj(V); // Add each edge in both directions since the graph is undirected for (int i = 0; i < edges.size(); i++) { adj[edges[i][0]].push_back(edges[i][1]); adj[edges[i][1]].push_back(edges[i][0]); } // Create a visited array to keep track of visited vertices vector<bool> vis(V, false); // Store the number of connected components int count = 0; // Traverse all vertices to find unvisited components for (int i = 0; i < V; i++) { // Start DFS when an unvisited vertex is found if (!vis[i]) { count++; // Traverse all vertices belonging to the current component dfsHelper(i, adj, vis); } } return count; }};// Driver code startsint main() { Solution sol; // Number of vertices in the graph int V = 7; // Store the edges of the undirected graph vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 3}, {4, 5}}; cout << "Number of Connected Components: " << sol.countComponents(V, edges) << endl; return 0;}Complexity Analysis
Time Complexity: O(V + E), where V is the number of vertices and E is the number of undirected edges. Building the adjacency list and running DFS together process every vertex and every adjacency-list entry; an undirected graph stores 2E neighbor entries, but the asymptotic bound remains O(V + E).
Space Complexity: The adjacency list uses O(V + E) input/storage space. The visited array and recursive DFS call stack use O(V) auxiliary space in the worst case, and the component counter uses O(1) space.
Alternative Approach: Disjoint Set Union
Disjoint Set Union can also solve this problem by treating each vertex as its own group at the start. For every edge, union the two endpoint vertices. Whenever an edge connects two different groups, the number of components decreases by one.
With path compression and union by size or rank, the complexity is O((V + E) × ALPHA(V)), where ALPHA is the inverse Ackermann function. This is effectively near-linear for all practical input sizes. DSU is especially useful when connectivity information must be updated or queried repeatedly.
Interview follow-up Questions
Yes, in the traditional sense. For directed graphs, the concept becomes much more complex because you can have a one-way path from A to B, but not from B to A. In directed networks, we specifically look for "Strongly Connected Components" using specialized algorithms like Kosaraju's or Tarjan's.
Be the first to add a comment.