并查集

简单并查集操作

初始化

定义数组$fa[~]$，$fa[i]$是元素$i$所属的并查集，未处理前每个点属于独立的集

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

查找

普通查找版（虽然无优化，但后续可以依靠启发式合并操作降低复杂度，并且在可撤销并查集中仍需使用）

int find_set(int x)
{
    if(x!=fa[x]) return find_set(fa[x]);
    return x;
}

优化-路径压缩版（适用于大部分并查集的查找）

int find_set(int x)
{
    if(x!=fa[x]) fa[x]=find_set(fa[x]);
    return fa[x];
}

合并

将$a$与$b$合并，即将$a$的父亲节点与$b$的父亲节点合并

void merge_set(int a,int b)
{
    a=find_set(a),b=find_set(b);
    if(a==b)
    {
	    //其余code
    }
    else
    {
        fa[b]=a;
        //其余code
    }
    
}

带权并查集

在基础并查集操作之上，定义一个权值数组$d[~]$,$d[i]$为节点$i$到父亲节点的权值

int find_set(int x)
{
    if(x!=fa[x])
    {
        int t=fa[x];
        fa[x]=find_set(fa[x]);
        d[x]+=d[t];                       //对权值进行操作
    }
}

void merge_set(int a,int b,int v)
{
    int roota=find_set(a), rootb=find_set(b);
    if(roota==rootb){
        if(d[a]-d[b]!=v) ans++;
    }
    else{
        fa[roota]=rootb;
        d[roota]=d[b]-d[a]+v;            //对权值进行操作
    }
}
//此为hdu-3038代码

种类并查集

种类并查集还称作为扩展域并查集的原因就是，它是通过拓展并查集$fa[~]$ 大小来处理种类关系。

敌人/朋友关系

域$1$~$n$：表示元素本身域($n+1$)~($2n$)：表示敌人（$i$的敌人->$i+n$）

$x$与$y$是朋友：合并$x$与$y$
$x$与$y$是敌人：合并$x$与$y+n$，同时合并$y$与$x+n$

rep(i,1,m)
{
	int x=a[i].u,y=a[i].v;
	if(find_set(x)==find_set(y))
	{
		cout<<a[i].w; return 0;
	}
	merge_set(x,y+n);
	merge_set(y,x+n);
}
//此为P1525关押罪犯代码

食物链模型

经典食物链问题，A吃B，B吃C，C吃A（如题目食物链）

域$1$~$n$：动物本身
域($n+1$)~($2n$)：食物区
域($2n+1$)~($3n$)：天敌区

可撤销并查集

多数不使用路径压缩，否则无法实现撤销操作，用启发式合并优化复杂度
将每次合并操作入栈$st$
撤销操作即为出栈，并将并查集状态恢复至入栈前时刻

初始化

int fa[N],n,ans[N];
int siz[N],cnt[N];
vector<int> nex[N];
struct node
{
    int a,b;
    int val;
}p[N];
stack<node> st;

查找

即暴力查找

int find_set(int x)
{
    if(x!=fa[x]) return find_set(fa[x]);
    return x;
}

启发式合并

意为将$size$值小的集合合并到$size$值大的集合
并将每次合并操作入栈

void merge_set(int a,int b)
{
    a=find_set(a),b=find_set(b);
    if(a==b)
    {
        sum-=get(a);
        cnt[a]++;
        sum+=get(a);
        st.push({a,a,0});
    }
    else
    {
        if(siz[a]<siz[b]) swap(a,b);        //启发式合并
        fa[b]=a;                            //启发式合并
        sum-=get(a)+get(b);
        siz[a]+=siz[b];
        cnt[a]+=cnt[b]+1;
        sum+=get(a);
        st.push({a,b,1});                   //操作入栈
    }
}
//此为abc302_h代码

撤销操作

将所需要撤销的操作出栈，并恢复至入栈前状态

void revert()
{
    auto [a,b,op]=st.top();
    st.pop();
    if(!op)
    {
        sum-=get(a);
        cnt[a]--;
        sum+=get(a);
    }
    else
    {
        sum-=get(a);
        cnt[a]-=cnt[b]+1;
        siz[a]-=siz[b];
        fa[b]=b;
        sum+=get(a)+get(b);
    }
}
//此为abc302_h代码