并查集

并查集，是用代表元素来维护一个集合的数据结构。可以差不多\(O(1)\)地查询两个元素是否在同一个集合内。

并查集主要通过路径压缩和按秩合并减小复杂度。单独用的话最坏复杂度都是\(O(logn)\)的（虽然只路径压缩的均摊复杂度还是差不多\(O(1)\)）。分开讲。

首先是初始化，每个元素各自属于自己的集合。

for(int i=1;i<=n;i++)fa[i]=i;

1. 路径压缩

我们发现，一个点无论是与它的代表节点相连还是与别的什么节点相连对最后的结果是没有影响的。也就是说，我们可以每次查询的时候把这个节点连到代表节点上，即路径压缩。

int find(int x){
    if(fa[x]!=x)fa[x]=find(fa[x]);//路径压缩
    return fa[x];
}

2. 按秩合并

资料里对这个秩的定义大概有两种：深度和集合大小。一般按照集合大小，即启发式合并。具体地说，小的扔到大的上。

void merge(int x,int y){
    x=find(x);y=find(y);
    if(size[x]<size[y])fa[x]=y;//x比较小 连到y上（其实一般不要这个） 
    else fa[y]=x;
}

然后是两个小应用。

1. 边带权

P1196 [NOI2002] 银河英雄传说

这个题要求两点间的距离。显然这个可以转成到最头上的点的距离，也就是并查集的代表元素。使用并查集。

求距离时我们使每条边带1的边权。具体地，我们把上边两个东西稍微改一下。

int find(int x){
    if(fa[x]==x)return x;
    int rt=find(fa[x]);
    dis[x]+=dis[fa[x]];//路径压缩时 fa[x]已经存储了到根节点的距离 直接加上就行 
    fa[x]=rt;return fa[x];
}
void merge(int x,int y){
    x=find(x);y=find(y);
    fa[x]=y;dis[x]+=size[y];
	size[y]+=size[x];size[x]=0;
}

2. 扩展域

P2024 [NOI2001] 食物链

这个题要维护三种关系：同类，天敌，食物。

我们可以开三倍大小的并查集，分别维护这三种关系。

当回答到x，y是同类时，x的同类与y的同类合并，x的食物与y的食物合并，x的天敌与y的天敌合并。

当回答到x吃y时，x的食物与y的同类合并，x的天敌与y的食物合并，x的同类与y的天敌合并。

void solve(int a){
	if(a==1){
		if(find(b+n)==find(c)||find(b+2*n)==find(c)){cnt++;continue;}
		merge(b,c);merge(b+n,c+n);merge(b+2*n,c+2*n);
	}
	if(a==2){
		if(b==c){cnt++;continue;}
		if(find(b)==find(c)||find(b+2*n)==find(c)){cnt++;continue;}
		merge(b,c+2*n);merge(b+n,c);merge(b+2*n,c+n);
	}
}