并查集

Update:2024-4-17 更改文章风格和代码优化

将两个集合合并为一个集合，并实现较短时间的信息查询与更新。

合并与查找（并查）

合并： 将两个集合归并为一个集合。

查找： 查询两个节点是否为同一个集合。

int find(int x)
{
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}
void add(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y) return;
	f[y]=x;
	return;
}

带权并查集

但有的 ~毒瘤~ 良心出题人会考复杂一点在合并集合的时候将权值一同进行合并。~一般~ 目前我做到的题目都是合并到祖先的距离。

代码（x所在集合接上y所在的末尾）

int a=f(x),b=f(y);
p[a].dis+=num[b];
p[a].fa=b;
num[b]+=num[a];
num[a]=0;

num数组是这个集合的总长度，dis是到祖先的距离，dis初始值为0，num为1。因为初始状态每个元素都是祖先，他们到祖先的距离为0，但每个集合都有一元素。

有的题可能是要合并距离的时候直接x接在y上，此时合并权值的部分只需要换成siz[x]+=siz[y]+1即可。

但有的题他可能并不只是维护一个集合，我们需要同时维护其他集合，比如敌人集合,但想起来复杂实现却比较简单。

if( m[q]==0 ) m[q]=find(p);
	else add(m[q],p);
if(m[p]==0) m[p]=find(q);
	else add(m[p],q);

其中m数组为敌人数组。如果合并的时候敌人的敌人不存在就我当这个敌人，反之就合并我和敌人的敌人，因为敌人的敌人是朋友，但朋友的朋友是敌人不需要刻意维护，他们的祖先是一样的。

合并优化

其实合并的过程我们可以看作是一个构建树的过程。其具体过程如下所示：

我们想要将7与5进行合并

由于路径优化，我们实现的时候进行的是$4->1$的操作。

而为了优化合并过程中，可能产生的时间问题，使得生成树深度最小化，我们将选择

code(团伙）

#include<bits/stdc++.h>
using namespace std;
int f[10012],m[10012],vis[10012],ans;

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

void add(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y) return;
	f[y]=x;
	return;
}



int main(){
	int n,l,q,p;
	char o;
	cin>>n>>l;
	for(int i=1;i<=n;i++)
		f[i]=i;
	while(l--)
	{
		cin>>o>>p>>q;
		if(o=='F')
			add(q,p);
		else{
			if( m[q]==0 ) m[q]=find(p);
			else add(m[q],p);
			if(m[p]==0) m[p]=find(q);
			else add(m[p],q);
		}
	}
	for(int i=1;i<=n;i++)
	{
		int j=find(i);
		if(!vis[j]) vis[j]++,ans++; 
	
	} 
	cout<<ans;
	
	
	
	
}