并查集

这篇博客讲的很nice 原地址
hdu1232
题意大概是有N个城市 城市之间有M条马路使他们两两相连 然后求还要加多少条路可以让所有的城市相通 这里的相通不一定是说两个城市之间直接相同 也可以路过其他的城市
先上代码 上面那篇博客讲的很清楚 例题也是这一题

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int fa[1050];
bool t[1050];
ll find(ll x){     
    return x==fa[x] ? x : (fa[x]=find(fa[x]));
}
void merge(ll a,ll b){
    int fx=find(a),fy=find(b);
    if(fx!=fy)
        fa[fy]=fx;
}
void inti(int n){
        for(ll i=1;i<=n;++i)
        fa[i]=i;
}
int main(void){
    ios::sync_with_stdio(false);
    ll N,M;
    while(cin>>N&&N){
        cin>>M;
        ll a,b;
        inti(i)
        for(ll i=1;i<=M;++i){
            cin>>a>>b;
            merge(a,b);
        }
        memset(t,0,sizeof(t));
        for(ll i=1;i<=N;++i)    //这一步就相当于标记每一个的父节点 最后只要统计父节点就可以了
            t[find(i)]=1;
        ll ans=0;
        for(ll i=1;i<=N;++i){
            if(t[i])
                ans++;
        }
        cout<<ans-1<<endl;
    } 
    return 0;
}

下面是按秩合并 原文地址
按秩合并的优势在于将简单的往复杂的上面合并 这样就可以有效地减低树的复杂度
按秩合并的改变加入了一个rank数组 用来记录每一个点的深度 这样就可以在合并时比较深度进行合并
初始化

inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}

然后是合并时

inline void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x!=y)
        rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}