Number of Connected Components In An Undirected Graph Problem
Number of Connected Components In An Undirected Graph Problem
Given an undirected graph with n nodes, an edges array is provided where edges[i] = [a, b] indicates an edge between node a and node b.
The nodes are numbered from 0 to n – 1. The task is to return the total number of connected components in the graph.
Examples related to Number of Connected Components In An Undirected Graph
Example 1:
edges=[[0,1], [0,2]]
Output: 1
Example 2:
edges=[[0,1], [1,2], [2,3], [4,5]]
Output: 2
Constraints:
- 1 <= n <= 100
- 0 <= edges.length <= n * (n – 1) / 2
Hints to solve Number of Connected Components In An Undirected Graph
Recommended Time & Space Complexity
Aim for a solution with a time complexity of O(V + E) and a space complexity of O(V + E), where V represents the number of vertices and E represents the number of edges in the graph.
Hint 1:
Initially, assume there are no edges, so we have n components, corresponding to the n nodes. Then, add the given edges between the nodes.
Can you think of an algorithm to add these edges?
After adding an edge, how do you calculate the number of remaining components?
Hint 2:
We can use the Union-Find (DSU) algorithm to add the edges. For simplicity, we use Union-Find by size, where the smaller component is merged into the larger one.
Union-Find algorithm only adds an edge between two nodes if they are from different components. If the nodes are already in the same component, the edge is not added.
How do you determine the number of components after adding the edges?
For example, if nodes 0 and 1 are initially disconnected (i.e., two components), adding an edge between them merges them into one component, reducing the total number of components.
Hint 3:
Create a DSU object and initialize the result variable, res = n, which represents the initial number of components.
Then, iterate through the given edges. For each edge, try to connect the nodes using the union function of the DSU.
If the union is successful, decrement res; otherwise, continue. Finally, return res as the total number of components.
Methods to Solve Number of Connected Components In An Undirected Graph Problem
There are mainly 3 approaches to solve Solve Number of Connected Components In An Undirected Graph Problem:
- Depth First Search
- Breadth First Search
- Disjoint Set Union (Rank | Size)
1. Depth First Search Method
Depth First Search (DFS): DFS explores the graph by starting from a node and visiting all reachable nodes, marking them as visited. It continues this process recursively for each unvisited node, counting the connected components as separate groups of connected nodes.
- Time complexity: O(V+E)
- Space complexity: O(V+E)
Where V is the number of vertices and E is the number of edges.
Code:
class Solution {
public:
int countComponents(int n, vector>& edges) {
vector> adj(n);
vector visit(n, false);
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
int res = 0;
for (int node = 0; node < n; ++node) {
if (!visit[node]) {
dfs(adj, visit, node);
res++;
}
}
return res;
}
private:
void dfs(const vector>& adj, vector& visit, int node) {
visit[node] = true;
for (int nei : adj[node]) {
if (!visit[nei]) {
dfs(adj, visit, nei);
}
}
}
};
public class Solution {
public int countComponents(int n, int[][] edges) {
List> adj = new ArrayList<>();
boolean[] visit = new boolean[n];
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
int res = 0;
for (int node = 0; node < n; node++) {
if (!visit[node]) {
dfs(adj, visit, node);
res++;
}
}
return res;
}
private void dfs(List> adj, boolean[] visit, int node) {
visit[node] = true;
for (int nei : adj.get(node)) {
if (!visit[nei]) {
dfs(adj, visit, nei);
}
}
}
}
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
adj = [[] for _ in range(n)]
visit = [False] * n
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
def dfs(node):
for nei in adj[node]:
if not visit[nei]:
visit[nei] = True
dfs(nei)
res = 0
for node in range(n):
if not visit[node]:
visit[node] = True
dfs(node)
res += 1
return res
class Solution {
/**
* @param {number} n
* @param {number[][]} edges
* @returns {number}
*/
countComponents(n, edges) {
const adj = Array.from({ length: n }, () => []);
const visit = Array(n).fill(false);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const dfs = (node) => {
for (const nei of adj[node]) {
if (!visit[nei]) {
visit[nei] = true;
dfs(nei);
}
}
};
let res = 0;
for (let node = 0; node < n; node++) {
if (!visit[node]) {
visit[node] = true;
dfs(node);
res++;
}
}
return res;
}
}
2. Breadth First Search
BFS explores the graph level by level, starting from a node and visiting all its neighbors before moving to the next level. It counts the connected components by ensuring each node is visited once, with each BFS call representing a new component
- Time complexity: O(V + E)
- Space complexity: O(V + E)
Where V is the number of vertices and E is the number of edges.
Code:
class Solution {
public:
int countComponents(int n, vector>& edges) {
vector> adj(n);
vector visit(n, false);
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
int res = 0;
for (int node = 0; node < n; ++node) {
if (!visit[node]) {
bfs(adj, visit, node);
res++;
}
}
return res;
}
private:
void bfs(vector>& adj, vector& visit, int node) {
queue q;
q.push(node);
visit[node] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int nei : adj[cur]) {
if (!visit[nei]) {
visit[nei] = true;
q.push(nei);
}
}
}
}
};
public class Solution {
public int countComponents(int n, int[][] edges) {
List> adj = new ArrayList<>();
boolean[] visit = new boolean[n];
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
int res = 0;
for (int node = 0; node < n; node++) {
if (!visit[node]) {
bfs(adj, visit, node);
res++;
}
}
return res;
}
private void bfs(List> adj, boolean[] visit, int node) {
Queue q = new LinkedList<>();
q.offer(node);
visit[node] = true;
while (!q.isEmpty()) {
int cur = q.poll();
for (int nei : adj.get(cur)) {
if (!visit[nei]) {
visit[nei] = true;
q.offer(nei);
}
}
}
}
}
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
adj = [[] for _ in range(n)]
visit = [False] * n
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
def bfs(node):
q = deque([node])
visit[node] = True
while q:
cur = q.popleft()
for nei in adj[cur]:
if not visit[nei]:
visit[nei] = True
q.append(nei)
res = 0
for node in range(n):
if not visit[node]:
bfs(node)
res += 1
return res
class Solution {
/**
* @param {number} n
* @param {number[][]} edges
* @returns {number}
*/
countComponents(n, edges) {
const adj = Array.from({ length: n }, () => []);
const visit = Array(n).fill(false);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const bfs = (node) => {
const q = new Queue([node]);
visit[node] = true;
while (!q.isEmpty()) {
const cur = q.pop();
for (const nei of adj[cur]) {
if (!visit[nei]) {
visit[nei] = true;
q.push(nei);
}
}
}
};
let res = 0;
for (let node = 0; node < n; node++) {
if (!visit[node]) {
bfs(node);
res++;
}
}
return res;
}
}
3. Disjoint Set Union (Rank | Size)
DSU tracks the connected components using a union-find approach, where nodes are grouped into sets. Using union by rank or size ensures efficient merging of components, and the number of connected components is determined by the number of distinct sets.
- Time complexity: O(V+(E∗α(V)))
- Space complexity: O(V)
Where V is the number of vertices and E is the number of edges.
Code:
class DSU {
public:
vector parent;
vector rank;
DSU(int n) {
parent.resize(n);
rank.resize(n, 1);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int node) {
int cur = node;
while (cur != parent[cur]) {
parent[cur] = parent[parent[cur]];
cur = parent[cur];
}
return cur;
}
bool unionSets(int u, int v) {
int pu = find(u);
int pv = find(v);
if (pu == pv) {
return false;
}
if (rank[pv] > rank[pu]) {
swap(pu, pv);
}
parent[pv] = pu;
rank[pu] += rank[pv];
return true;
}
};
class Solution {
public:
int countComponents(int n, vector>& edges) {
DSU dsu(n);
int res = n;
for (auto& edge : edges) {
if (dsu.unionSets(edge[0], edge[1])) {
res--;
}
}
return res;
}
};
public class DSU {
int[] parent;
int[] rank;
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int node) {
int cur = node;
while (cur != parent[cur]) {
parent[cur] = parent[parent[cur]];
cur = parent[cur];
}
return cur;
}
public boolean union(int u, int v) {
int pu = find(u);
int pv = find(v);
if (pu == pv) {
return false;
}
if (rank[pv] > rank[pu]) {
int temp = pu;
pu = pv;
pv = temp;
}
parent[pv] = pu;
rank[pu] += rank[pv];
return true;
}
}
public class Solution {
public int countComponents(int n, int[][] edges) {
DSU dsu = new DSU(n);
int res = n;
for (int[] edge : edges) {
if (dsu.union(edge[0], edge[1])) {
res--;
}
}
return res;
}
}
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1] * n
def find(self, node):
cur = node
while cur != self.parent[cur]:
self.parent[cur] = self.parent[self.parent[cur]]
cur = self.parent[cur]
return cur
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv:
return False
if self.rank[pv] > self.rank[pu]:
pu, pv = pv, pu
self.parent[pv] = pu
self.rank[pu] += self.rank[pv]
return True
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
dsu = DSU(n)
res = n
for u, v in edges:
if dsu.union(u, v):
res -= 1
return res
class DSU {
/**
* @param {number} n
*/
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = Array(n).fill(1);
}
/**
* @param {number} node
* @return {number}
*/
find(node) {
let cur = node;
while (cur !== this.parent[cur]) {
this.parent[cur] = this.parent[this.parent[cur]];
cur = this.parent[cur];
}
return cur;
}
/**
* @param {number} u
* @param {number} v
* @return {boolean}
*/
union(u, v) {
let pu = this.find(u);
let pv = this.find(v);
if (pu === pv) {
return false;
}
if (this.rank[pv] > this.rank[pu]) {
[pu, pv] = [pv, pu];
}
this.parent[pv] = pu;
this.rank[pu] += this.rank[pv];
return true;
}
}
class Solution {
/**
* @param {number} n
* @param {number[][]} edges
* @returns {number}
*/
countComponents(n, edges) {
const dsu = new DSU(n);
let res = n;
for (const [u, v] of edges) {
if (dsu.union(u, v)) {
res--;
}
}
return res;
}
}
