inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
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]++;
}

例题

（洛谷P1551）亲戚
洛谷P3958 奶酪）

L2-007 家庭房产 (25 分)

#include<bits/stdc++.h>
using namespace std;
int co;//关系的数量
int n;//数据量
const int N = 1e4+5;
struct edfe{
    int a,b;//关系先记入这里面
}e[N];
bool st[N];//有一个人的家庭，需要特殊处理
//并查集
//家庭代表（这里需要是id最小的），人数，房屋数量，房屋面积
int fa[N],peo[N],avgs[N],avga[N];
int find(int x){
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
void unionf(int a, int b){
    int faa=find(a),fbb = find(b);
    if(faa!=fbb){//还没有记为一个家庭的话
      fa[max(faa,fbb)] = min(faa,fbb);//将id较小的设置为父亲  
      peo[min(faa,fbb)]+=peo[max(faa,fbb)];//将人数加到id较小的人数里面存着
      avgs[min(faa,fbb)]+=avgs[max(faa,fbb)];//房屋数量，同上
      avga[min(faa,fbb)]+=avga[max(faa,fbb)];//房屋面积，同上
    }
}
struct family{
    int id,cnt,avgs,avga;
    //重载运算符，为了下面的sort
    bool operator <(family x){
        if(x.cnt*avga==cnt*x.avga){
            return id<x.id;
        }
        return x.cnt*avga>cnt*x.avga;
    }
};
int main()
{
    ios::sync_with_stdio(false);
    //初始化
    for(int i =0;i<N;i++){
        fa[i]=i,peo[i]=1;
    }
    cin>>n;
    int id, father,mother, k;
    for(int i =0;i<n;i++){
        cin>>id>>father>>mother>>k;
        if(father!=-1)e[co++]={id,father};
        if(mother!=-1)e[co++]={id,mother};
        st[id]=true;//有些家庭可能就只有一个人，需要特殊标记
        int kid;
        for(int j=0;j<k;j++){
            cin>>kid;
            e[co++]={id,kid};
        }
        cin>>avgs[id]>>avga[id];
    }
    //开始处理刚刚接收的各个关系
    for(int i =0;i<co;i++){
        int a=e[i].a,b=e[i].b;
        st[a]=st[b]=true;
        unionf(a,b);
    }
    vector<family> ans;
    for(int i =0;i<N;i++){
        //如果这个人存在，并且是家庭代表，就加入ans
        if(st[i] && fa[i]==i){
            ans.push_back({i,peo[i],avgs[i],avga[i]});
        }
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(auto t:ans)
        printf("%04d %d %.3lf %.3lf\n",t.id,t.cnt,(double)t.avgs/t.cnt,(double)t.avga/t.cnt);
    return 0;
}

巧妙利用并查集——L2-013 红色警报 (25 分)

用并查集，先计算出开始时父节点指向自己的点（也就是这一个连通块的代表），数量记为num（连通块的数量），随后每次输入城市都重新计算这类点的数量numx与初始值比较，如果numx>num说明连通性改变了，每次都要更新num的值为numx
详细看注释。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//并查集
ll fa[505]; //连通的记录在一块，代表随意，只是为了方便算 块数
ll lost[505] = {0};//记录被攻陷的城池
struct e{//边的关系
    ll a,b;
};
vector<e> ev;
//初始化fa
void init(){
    for(ll i =0;i<505;i++){
        fa[i] = i;
    }
}
ll find(ll a){
    return a == fa[a] ? a : (fa[a] = find(fa[a]));
}
void merge(ll x,ll y){
    ll a = find(x);
    ll b = find(y);
    if(a != b){
        fa[a] = b;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    ll n,m;cin>>n>>m;
    init();
    ev.resize(m);
    for(int i = 0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        ev[i] = {a,b};
        merge(a,b);
    }
    ll num = 0;
    for(ll i = 0 ;i<n;i++){
        if(fa[i] == i)//代表自己，说明自己就是那一块的代表
            num++;
    }
    ll k;cin>>k;
//     cout<<"k="<<k<<"\n";
    while(k--){
        ll x;cin>>x;
        lost[x] = 1;
        init();
        ll numx = 0;
        for(int i =0;i<m;i++){
            if(lost[ev[i].a]==0 && lost[ev[i].b]==0){//操作在ev中记录过的
                merge(ev[i].a,ev[i].b);
            }
        }
        //再算一遍有几个块
        for(int i = 0;i<n;i++){
            if(fa[i]==i && lost[i]==0)numx++;//自己是块代表，并且自己没给攻占
        }
        if(numx>num){//块的数量增加了的话，就说明整个国家的连通性改变了
            cout<<"Red Alert: City "<<x<<" is lost!"<<endl;
        }else{
            cout<<"City "<<x<<" is lost."<<endl;
        }
        if(numx==0){
            cout<<"Game Over."<<endl;
        }
        num=numx;//更新初始值
    }
    return 0;
}

L3-003 社交集群 (30 分)

主要是每个人 都有各种兴趣爱好，只要两个人有相同的一个兴趣爱好，就能是一个社群——也就意味着 即使有两人可能完全没有一个兴趣，但有其他人作为中间人，就会成为一个社群的人。所以需要每个兴趣编号都有一个 第一人——所有后来有这个兴趣的，都是跟随他 （的父节点）—— 加入父节点也就是加入了该社群。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i =n;i<m;++i)
//并查集
vector<int> root;//root[i]==0时代表i不是根节点，否则存储的该社群的人数
vector<int> f;//father
int course[1005];//course[t] 存储第一个喜欢该课的人，后面的人都是追随他
// int find(int x){
//     int t = x;
//     while(x != f[x]){
//         x = f[x]; //找到x社群最上面的根节点
//     }
//     //此时x已经变为原先x的根节点了
//     while(t != f[t]){
//         f[t] = x;//路上的所有兄弟都要跟随跟节点
//         t = f[t];        
//     }
//     return x;//返回根节点
// }
int find(int x){
    return x == f[x] ? x : (f[x] = find(f[x]));
}
void merge(int a, int b){
    int fa = find(a),
        fb = find(b);
    if(fa != fb){
        f[fa] = fb;//将a的根节点改为b的根节点
    }
}
int _cmp(int a, int b){ //后面排序要用
    return a > b;
}
int main()
{
    ios::sync_with_stdio(false);
    int n, k, t, 
        cnt = 0;//社群数
    char c;//读那个冒号
    cin>>n;
    f.resize(n+1);
    root.resize(n+1);
    for(int i = 1; i <= n; i++)
        f[i] = i;
    for(int i = 1; i<= n; i++){
        cin>>k>>c;
        for(int j = 0;j<k;j++){
            cin>>t;
            if(course[t] == 0){ //说明没有前人，那i就当第一人
                course[t] = i;
            }
            merge(i, find(course[t]) );//i直接跟随第一人的根节点
        }
    }
    for(int i = 1;i<=n;i++){
        root[find(i)] ++;
    }
    for(int i = 1;i<=n;i++){
        if(root[i] != 0)
            cnt++;
    }
    cout<<cnt<<"\n";
    sort(root.begin() ,root.end(), _cmp);
    for(int i = 0;i<cnt;i++){
        cout<<root[i];
        if(i != cnt - 1)
            cout<<" ";
    }
    return 0;
}