并查集

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

初始化：

fa[i]=i;

Find:

无压缩

int Find(int x) {
    if(fa[x]==x) return x;
    else return Find(fa[x]);
}

压缩

int Find(int x) {
//    if(x!=fa[x]) fa[x]=Find(fa[x]);
//    return fa[x];
    return x==fa[x] ? x : (fa[x]=Find(fa[x]));//简写
}

Union：

void Union(int x,int y) {
    fa[Find(x)]=Find(y);
}

例（洛谷P1551）：

https://www.luogu.com.cn/problem/P1551

#include<bits/stdc++.h>
using namespace std;
int fa[5005];
int Find(int x) {
//    if(x!=fa[x]) fa[x]=Find(fa[x]);
//    return fa[x];
    return x==fa[x] ? x : (fa[x]=Find(fa[x]));
}
void Union(int x,int y) {
    fa[Find(x)]=Find(y);
}
int main() {
    int n,m,p;
    cin>>n>>m>>p;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i) {
        int x,y;
        cin>>x>>y;
        Union(x,y);
    }
    for(int i=1;i<=p;++i) {
        int x,y;
        cin>>x>>y;
        if(Find(x)==Find(y)) {
            cout<<"Yes\n";
        }
        else cout<<"No\n";
    }
}