Problem 49: Union-Find Connected Components
Problem Statement: Given an undirected graph with n nodes and m edges, determine the number of connected components using the union-find data structure.
Input
The first line contains two integers n and m. Each of the next m lines contains two integers u and v representing an edge between u and v.
Output
Print the number of connected components.
Examples
Input:
5 2
1 2
4 5
Output:
3
Solution Explanation
Method 1: Use Union-Find (Disjoint Set Union) data structure to unite nodes that are connected and then count the remaining unique sets. Method 2: Use graph traversal (DFS or BFS) marking visited nodes to count separate connected components, but union-find is more efficient for multiple queries.
Solution in C++
#include
#include
using namespace std;
int findp(int a, vector &parent){
return parent[a] == a ? a : parent[a] = findp(parent[a], parent);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
vector parent(n+1);
for (int i = 1; i <= n; i++) parent[i] = i;
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
int pu = findp(u, parent);
int pv = findp(v, parent);
if(pu != pv){
parent[pu] = pv;
}
}
int count = 0;
for(int i = 1; i <= n; i++){
if(findp(i, parent) == i) count++;
}
cout << count << "
";
return 0;
}