本文主要以模板为主。

简介

并查集是一种树型的数据结构，用于处理一些不相交集的合并及查询问题。不相交集，就是交集为空集的一些集合。比如集合 $\{1,3,5\}$ 和集合 $\{2,4,6\}$ 就是不相交集。 $\{2,3,5\}$ 和 $\{ 1,3,5\}$ 就不是，因为他们的交集不是空集。

形象地来说，有点像“朋友圈”：A 和 B 是朋友，A 和 B 就构成了一个朋友圈，C 和 D 是朋友，C 和 D 也构成了一个朋友圈，那么这时，如果 B 和 C 成为了朋友，A、B、C、D 就构成了一个大的朋友圈。

并查集就是可以描述这种情形的数据结构。

模板

仅使用“路径压缩”优化版。

struct UFDS
{
	ll dad[M],n;
	void init(ll p){ n=p; for(ll i=1;i<=n;i++) dad[i]=i; }
	ll find(ll x)
	{   
   		while(x!=dad[x])
      		x=dad[x]=dad[dad[x]];
 		return x;
	}
	void union_(ll x,ll y)
	{
   		ll d1=find(x),d2=find(y);
   		dad[d1]=d2;
   		return;
	}
	bool check(ll x,ll y)
	{
   		ll d1=find(x),d2=find(y);
   		if(d1==d2)
       		return 1;
   		return 0;
	}
}ufds;

操作

对于并查集，主要有如下操作：

初始化。
合并两个集合（并）。
判断两个元素是否属于同一个集合（查）。

初始化

void start(int n)
{
	for(int i=1;i<=n;i++)
		dad[i]=i;
	return;
}

dad也是父亲的意思。。。

并

void union_(int x,int y)
{
	int d1=find(x),d2=find(y);
	dad[d1]=d2;
	return;
}

查————代表

递归式

int find(int x)
{
	if(dad[x]==x)
    	return dad[x];
    return find(dad[x]);
}//注意可能会RE

非递归式

int find(int x)
{  
    int root=x;  
    while(root!=dad[root])
        root=dad[root];
    return root;  
}

查————是否在同一集合

bool check(int x,int y)
{
	int d1=find(x),d2=find(y);
	if(d1==d2)
		return 1;
	return 0;
}

优化

路径压缩

递归式

int find(int x)
{
	if(dad[x]==x)
    	return dad[x];
    return dad[x]=find(dad[x]);//<---
}//递归式

非递归式

int find(int x)
{   
    while(x!=dad[x])
        x=dad[x]=dad[dad[x]];
    return x;
}

路径压缩的效率很高（一次操作时间复杂度为 $O(\alpha(m,n))$ ，可看作很小的常数），可以防止树的形态变为一条链。在一般并查集中应用很广泛，一旦使用路径压缩，原有的父子关系就会被破坏，从而直接建立与祖先的父子关系，可以高效地维护集合之间的从属关系，但是对于每个节点之间的直接关系是不能维护的。

按秩合并

void start(int n)
{
    for(int i=1;i<=n;i++)
        dad[i]=i,rank[i]=0;//树的高度为0
    return;
}
void union_(int x,int y)
{
    int d1=find(x),d2=find(y);
    if(d1==d2) 
        return;
    if(rank[d1]>rank[d2])
        swap(d1,d2);
    dad[d1]=d2;    
    if(rank[d1]==rank[d2])//如果相等，只能增加树高
        rank[d2]++;
    return;//否则树高是不增加的
}