Connected Components

32
0

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 6 is 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 V vertices using the given edges.

  • Initialize a visited array of size V with all values set to false and set count = 0.

  • Traverse every vertex i from 0 to V - 1 and 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 count as the total number of connected components.

Dry Run

connected component bfs

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 starts
int 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 V vertices using the given edges.

  • Initialize a visited array of size V with all values set to false and set count = 0.

  • Traverse every vertex i from 0 to V - 1 and skip it if it has already been visited.

  • When an unvisited vertex is found, increment count and 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 count as the total number of connected components.

Dry Run

connected component dfs

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 starts
int 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.

Graph

Read Similar Blogs

Comments0