并查集实现连通图的检测

并查集的板子，一开始不会做，后来多做了几道就差不多会了。
普通并查集只是顺序的节点号。但是本题给出的节点号不是顺序的，所以这里没有采用数组的方式，而是采用了map散列表的方式。当然通过dfs也可以很好的解决这个题目。通过对所有节点进行dfs。只要没有全遍历到，那就sum++；

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
map<int,int> father;  //通过散列表map实现的father数组
map<int,int> height;  //记录每个节点的高度
int find(int x){
    if(father.find(x)!=father.end()){
        if(father[x]!=x)
            father[x]=find(father[x]);  //路径压缩(最后自己通过例子模拟下过程)
    }
    else{//如果还没有出现的新节点。把father设成他自己(表示根节点)，height设成0
        father[x]=x; 
        height[x]=0; 
    } 
    return father[x];
} 
void Union(int a,int b){//合并函数
    a=find(a);
    b=find(b);
    if(a!=b){
        if(height[a]>height[b])
            father[b]=a;
        else if(height[b]>height[a])
            father[a]=b;
        else{
            father[a]=b;
            height[a]++;
        }
    }
}
int main()
{
    int i,j;
    while(cin>>i>>j){
        //if(i==0)break;
        Union(i,j);
    }
    int sum=0;
    for(auto it=father.begin();it!=father.end();it++){
        if(it->first==it->second)sum++;  //只要有一个父亲是本身的就说明是根节点
    } 
    cout<<sum<<endl;
    return 0;    
}