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

它所处理的是“集合”之间的关系,即动态地维护和处理集合元素之间复杂的关系,当给出两个元素的一个无序(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;

 


欢迎来到睿屿青衫丶

avatar
 
微笑晕爱心心碎调皮难过尴尬惊讶惊吓酷泪奔吐彩虹害羞敲打喝彩抠鼻吐星星眼擦汗大笑蛋糕呲牙瞌睡咒骂吃瓜贪财骷髅鬼脸委屈奋斗笑哭摸头小纠结点赞笑崩发呆绿帽狂汗亲嘴么么机智抑郁色鄙视坏笑白眼左哼哼右哼哼捂嘴鼓掌可怜香肠嘴闭嘴墨镜认错思考拒绝鲜花愤怒嘟嘴不忍直视嘘emm流泪yeah睡觉扔鞋石化生病抽烟吐血偷笑衰兔牙害怕震惊捂嘴笑打盹疑问亲亲指开心喜欢阴险郁闷坏笑2搞怪汪好奇汪机智汪冷漠汪搞怪哈摆拍柴柴犬生气柴流泪柴张嘴柴挥爪柴佩服勾引拳头胜利赞踩滑稽
  订阅  
提醒