你需要了解一下什么叫并查集

它所处理的是“集合”之间的关系,即动态地维护和处理集合元素之间复杂的关系,当给出两个元素的一个无序对(a,b)时,需要快速“合并”a和b分别所在的集合,这其间需要反复“查找”某元素所在的集合。“并”、“查”、“集”三字由此而来。

在这种数据类型中,n个不同的元素被分为若干组,每组是一个集合,这种集合叫做分离集合(disjoint set)。并查集支持①查找一个元素所属的集合②合并两个元素各自所属的集合

每个集合需要一个元素当“代表”,不然你哪知道谁和谁一队呢?“代表”由谁来当是无所谓的,但是我们必须保证不修改集合时每个集合的代表不变(除非合并集合时有一个代表“变队”)。

集合可以通过多种方法实现,用的最多的是数组实现。

可我还是不懂并查集有啥用

假如给你若干组数据告诉你,一群人当中某两人之间有血缘关系,到最后你能不能判断任意两人有没有血缘关系呢?把有血缘关系的人放入同一个集合,到最后只需要看看这两人在不在一个集合,就可以知道他们有没有血缘关系了。而并查集处理的就是集合之间的关系。

想一些“笨办法”来实现程序不行吗?可行,如果你愿意面对庞杂的代码,以及半天跑不出结果的程序。。。

我不会告诉你,并查集有点高效哦

那我就来说说并查集支持的操作吧
建立新集合 (father[i]=i)

从1到n每个元素都在自己的集合里面,即:

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

这个father数组就是集合(可以定义别的名称,只是一般都这么定义)

合并集合(unionn)

如果之前两个集合是分离的,把他们合并成一个集合。

实现:把第二个集合的代表换成第一个集合中的元素

指向集合代表(find)

返回一个指向包含x的集合的代表

来贴代码
inline int find(int xx)
{

if(father[xx]!=xx) father[xx]=find(father[xx]);
return father[xx];

}
inline void unionn(int xx,int yy)
{

int f1=find(xx);
int f2=find(yy);
father[f2]=f1;
return;

}

    for(int i=0;i<=n+1;i++)
     father[i]=i;
最后修改:2022 年 03 月 04 日
如果觉得我的文章对你有用,请随意赞赏