并查集是一种高级的数据结构，它能够很好的解决

1. 将两个元素合并
2. 询问两个元素是否在一个集合内

同时可以额外维护很多信息

基本原理

每个集合用一颗树来表示，树根的标号就是集合的编号，每个节点存储其父节点的编号，使用p[x]存储父节点

问题

1. 如何判断树根

p[x]==x;

2. 如何求x的集合编号

while(p[x]!=x) x=p[x];

3. 如何合并两个集合

// 将x集合根节点的父元素置为y集合的根元素
p[x]=y

优化

在求x的集合编号时，每次都要遍历到根节点，时间和树的深度成正比 可以在第一次遍历之后，将这条路径上的元素的父节点都直接指向根节点，这样并查集的时间复杂度就近乎O(1)了

实现

合并集合

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e6;
int p[N];

int find(int x){
    // 这里使用到了路径压缩
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main() {
    int n,m;
    cin>>n>>m;
    // 将集合中每个点都初始化为根节点
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--){
        char s;
        int a,b;
        cin>>s;
        cin>>a>>b;
        if(s=='M'){
            p[find(a)]=find(b);
        }
        else {
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

题目

连通块中点的数量

1. 此题核心是用并查集维护一个cnt数组，存放集合中元素的数量
2. 如果两个集合合并，就将被合并集合的根元素的cnt加到合并集合的根元素cnt上
3. 这样我们就能维护一个cnt数组，记录每一个集合元素的个数

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N=1e6;

int p[N],cnt[N];                 


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

int main() 
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        p[i]=i;
        // 每个连通块刚开始只有自己，所以初始化为一
        cnt[i]=1;
    }
    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;;
            a=find(a),b=find(b);
            if(a!=b) 
            {
                p[a]=b;
		 //cnt对于祖宗节点才有用，每当合并两个集合，需要对应合并cnt
                cnt[b]+=cnt[a];         
            }
        }
        else if (s=="Q1")
        {
            cin>>a>>b;
            a=find(a),b=find(b);
            if(a==b) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            a=find(a);
            cout<<cnt[a]<<endl;
        }
    }
    return 0;
}

食物链

维护一个并查集，并且记录每个节点到根节点的距离，比较两个动物的关系时，只需要让距离余3，余数是1的吃余数是0的，依次类推

#include <iostream>
using namespace std;
const int N=50010;
int n,k;
int p[N],d[N];


int find(int x)
{
    if(x!=p[x])
    {
        // 在路径压缩中，维护d数组，保存元素到根节点的距离
        int u=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=u;
    }
    return p[x];
}

int main()
{
    cin>>n>>k;
    // 并查集的初始化不可忽略，d数组中每个节点到自己的距离为0，不需要初始化
    for (int i = 0; i < n; i ++ ) p[i] = i;
    int res=0;
    while(k--)
    {
        int t,x,y;
        cin>>t>>x>>y;
        if(x>n||y>n) res++;
        else
        {
            int px=find(x),py=find(y);
            // 如果祖宗节点相同，那么说明两个元素在同一个集合内，那么判断他们取余3的数字即可判断
            // 如果不同，就需要将两个集合合并，重新计算距离
            if(t==1)
            {
                if(px==py&&(d[x]-d[y])%3) res++;
                else if(px!=py) // 此处条件不能删
                {
                    p[px]=py;
                    d[px]=d[y]-d[x];
                }
            }
            else 
            {
                if(px==py&&(d[x]-d[y]-1)%3) res++;
                else if(px!=py)
                {
                    p[px]=py;
                    d[px]=d[y]-d[x]+1;
                }
            }
        }
    }
        
    cout<<res;
    return 0;
}