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;
}