In this problem, you are tasked with finding the number of connected components in an undirected graph. A connected component is a subset of nodes such that every pair of nodes in the subset is connected either directly or indirectly, and no additional nodes outside the subset are connected to the nodes in the subset.
For example:
- If the graph is fully connected, there is only 1 connected component.
- If the graph has isolated groups of nodes, each group is its own component.
This problem is common in graph theory and is fundamental for understanding graph traversal techniques like Depth-First Search (DFS), Breadth-First Search (BFS), and Union-Find.
Brute Force Approach
A brute force approach would involve repeatedly visiting all nodes in the graph and marking them as visited using DFS or BFS. Each unvisited node starts a new connected component.
import java.util.*;
public class ConnectedComponentsBruteForce {
public int countComponents(int n, int[][] edges) {
boolean[] visited = new boolean[n];
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.put(i, new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
count++;
dfs(i, graph, visited);
}
}
return count;
}
private void dfs(int node, Map<Integer, List<Integer>> graph, boolean[] visited) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, graph, visited);
}
}
}
}• Graph Construction: Build an adjacency list representation of the graph.
• DFS Traversal: For every unvisited node, perform a DFS to mark all reachable nodes as visited.
• Count Components: Each unvisited node represents a new connected component.
Time Complexity: O(V + E), where V is the number of nodes and E is the number of edges.
Space Complexity: O(V + E), for the adjacency list and visited array.
Optimized Approach
The optimized solution uses the Union-Find (Disjoint Set) algorithm to determine connected components efficiently. Union-Find is well-suited for this problem because it allows us to quickly group nodes into connected components and check if two nodes are in the same component.
Algorithmic and Data Structure Pattern
• Union-Find:
• The find operation determines the root of a node.
• The union operation merges two components.
• Path compression and union by rank optimize these operations, ensuring nearly constant time complexity.
public class ConnectedComponents {
public int countComponents(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
return uf.getCount();
}
}
class UnionFind {
private int[] parent;
private int[] rank;
private int count;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
count = size;
for (int i = 0; i < size; i++) {
parent[i] = i; // Each node is its own parent initially
rank[i] = 1; // Rank is initialized to 1
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count--; // Reduce the number of connected components
}
}
public int getCount() {
return count;
}
}Line-By-Line Explanation
Step 1: countComponents
public int countComponents(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
return uf.getCount();
}- Iterates through edges array.
- For each edge, it unions the two connected nodes.
- This method calculates the number of connected components in a graph using the Union-Find data structure
Step 2: UnionFind Constructor
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
count = size;
for (int i = 0; i < size; i++) {
parent[i] = i; // Each node is its own parent initially
rank[i] = 1; // Rank is initialized to 1
}
}- Each node is its own parent initially
- Each node starts with a rank of 1.
- Tracks the number of connected components, starting with size.
Step 3: UnionFind find method
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}- Finds the root of a node and applies path compression to flatten the structure for faster future queries.
Step 4: UnionFind union method
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count--; // Reduce the number of connected components
}
}- Calls to find method determine the root of the sets that nodes x and y belong to.
- If roots are the same, no further action need.
- If roots are not same, compare the rank of roots x and y.
- If rootX rank is greater, rootY is attached to rootX.
- If rootY rank is greater, rootX is attached to rootY.
• If both roots have the same rank:
• Attach rootY to rootX .
• Increment the rank of rootX because the height of the tree increases.
Why This Code Works
The Union-Find algorithm for counting connected components is a robust and efficient solution, leveraging path compression and rank optimization to handle even large graphs effectively. It provides a deeper understanding of graph connectivity, offering a versatile tool for solving graph problems in competitive programming and real-world applications like network analysis and clustering.
