并查集

概念：并查集是一种可以动态维护若干个不重叠的结合,并且支持合并与查询的数据结构.也就是擅长维护各种各样的具有传递性质的关系.
数据结构：使用树形结构存储每个集合,刚开始的时候每个点就是一个独立的集合,且这个集合树的树根就是本身.

初始化：把所有的父节点指向本身

void initial()
{
    for(int i=1;i<=n;i++) p[i]=i;
}

朴素做法找父节点：

int find(int x)
{
    if(x==p[x]) return x;
    else return find(p[x]);
}

路径优化的写法

    int find(int x)
    {
        return x==p[x]? x:p[x]=find(p[x]);
    }

合并集合

    void merge(int x,int y)
    {
        p[find(x)]=find(y);
    }

判断两数是否在一个集合/连通块内

    if(find(x)==find(y)) return true;
    else return false;

统计集合/连通块数量

    for(int i=1; i<=n; i++)
    {
        if (!vis[find(i)])//统计集合个数
        {
            vis[find(i)]++;
            cnt++;
        }
    }
    return cnt;

例题：acwing1249

 #include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int N=1e6+10;
int p[N];
int f(int x){
   return x==p[x]? x:p[x]=f(p[x]);
}
int main()
{
    scanf("%d %d",&n,&m);
    while(n--)p[n]=n;
    while(m--){
        int a,b;
        scanf("%d %d",&a,&b);
        p[f(a)]=f(b);
    }
    scanf("%d",&q);
    while(q--){
        int x,y;
        scanf("%d %d",&x,&y);
        if(f(x)==f(y)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}