并查集

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。并查集通常包含两种操作，查找，合并。
模板代码：
朴素并查集+路径压缩优化:

int find(int x)
{
    if(p[x]!=x) p[x]= find(p[x]);
    return p[x];
}
//p[x]存储每个点的祖宗节点。
//find(x)返回x的祖宗节点。
// 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
    p[find(a)] = find(b);

并查集同时还可以维护同一类别节点数量。

int size[N];//存储节点数量数组。size[i]表示第i个集合的节点数量。
// 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

也可以同时维护到祖宗节点的距离。

int p[N], d[N];//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
  if (p[x] != x)
  {
     int u = find(p[x]);
     d[x] += d[p[x]];
     p[x] = u;
   }
   return p[x];
}
   // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

例题：https://www.acwing.com/problem/content/242/
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =50005;
int p[N];
int d[N];
int find(int x)
{
    if(p[x]!=x) 
    {
        int t = find(p[x]);
        d[x]+=d[p[x]];
        p[x]=t;
    }
    return p[x];
}
int main(void)
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) p[i] = i;
    int t,x,y;
    int ans=0;
    while(k--)
    {
        cin>>t>>x>>y;
        if(x>n || y>n)++ans;
        else//不冲突即为真话。
        {
            int px= find(x);
            int py =find(y);
            if(t==1)
            {
                if(px==py && (d[x]-d[y])%3!=0)//已经在一个集合里面， t==1 (d[x]%3 != d[y]%3) 不为0 即，x,y不为同类。
                {
                    ++ans;//假话增加。
                }
                else if(px!=py)//x,y不属于同一个集合。 将x,y更新到同一个集合当中。
                {
                    p[px] = py;
                    d[px] = d[y]-d[x];//距离更新，满足(d[x]+d[px]-d[y])%3==0,更新为同类。
                }
            }
            else
            {
                if(px==py && (d[x]-d[y]-1)%3!=0) ans++;//x,y在同一个集合当中。若x吃y，则 (d[x]-d[y]-1)%3==0,反之为假话。
                else if(px!=py) //x,y不属于同一集合，将x,y更新到同一个集合当中。
                {
                    p[px] = py;
                    d[px] = d[y]+1-d[x];//距离更新，满足(d[x]-d[y]-1+d[px])%3==0 使得x吃y。
                    
                }
            }
            
        }
    }
    cout<<ans<<endl;
    
}