并查集

高级版

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int father[N];//父亲
int n,m,a,b;
int rank[N];//树的高度
int find(int x)//查询树的根
{
    if(x==father[x]) return x;
    else return father[x]=find(father[x]);
}
void Merge(int a,int b)//合并a和b所属的集合
{
    int pa=find(a);
    int pb=find(b);
    if(pa==pb) return;
    if(rank[pa]<rank[pb])  father[pa]=pb;
    else {
        father[pb]=pa;
        if(rank[pa]==rank[pb]) rank[pa]++;
    }
}
bool same(int a,int b)//判断a和b是否属于同一集合
{
    return find(a)==find(b);
}

并查集

原文：http://blog.csdn.net/u013050857/article/details/45288569