• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

Union collection,顾名思义,就是合并查找集合:

对于集合S={a1,a2,an-1,an},我们可以进一步把集合S分成: S1,S2,Sm-1,Sm。我们希望能够快速确定S中的任意两个元素是否属于S的同一个子集。

有两种主要操作:

1、Find:查找元素所属集合

Union:合并两个集合成一个新的集合

基本解析:

这组数据结构3354可以由树来表示。起初,每个元素都是一个集合。ihccnjaodym5201.png

那么如果我们现在想把{0}和{1}合并成集合{0,1}呢?然后自定义使用Union函数(具体代码实现下面会提到)。

但是,如果我想确定两个元素是否在同一个集合中,我可以使用Find函数。

代码思想:

首先,定义一个父数组来表示元素的父节点。

因为每个集合都有一个以Find操作.开始的根节点

int find(int x)

{

返回parent[x]==x?x : find(parent[x]);

}

这就是find操作,值得注意的是,所以对于任意两个元素,我们只要看他们所属的集合(树)的leader(根结点)是否是一样的就可以判断他们是否在同一个集合内.最后,我们可以通过比较find[x]是否等于find[y]来判断X和Y是否在同一个集合中(有相同的根节点)。

那么如何实现如果x=parent[x],那就说明已经找到了根结点。那就可以跳出并返回自己了。(也就是元素的根节点)?呢

传入两个元素,分别找到根节点,使根节点p1的父节点为p2,即p1在union操作.上

void to_union(int x1,int x2)

{

int P1=find(x1);

int p2=find(x2);

parent[P1]=p2;

}

哈哈,大家都懂,但是不要太高兴!

用脚趾头想想,每个查找操作的复杂度就是树的高度o(h)。如果树的每个节点(除了根节点和叶节点)只有一个度和一个条目,根节点的这棵树合并到p2为根节点的树

这不是AC人的标准,为什么不呢?

1mbaviwztbs5202.png

那么那很好,你就得到了o(n)的复杂度。。。将成为方法一:!

“路径压缩”。在执行Find的过程中,路径上的所有节点都直接连接到根节点。

路径压缩

实际上,当两棵树被合并时,方法二:"按秩合并".在这里,我们用“秩”代替高度,而秩代表高度的上限。通常,我们使只有一个节点的树的秩为0。严格来说,秩1是身高的上界;具有r1和r2等级的两棵树被合并。如果秩不相等,我们将把秩较小的树合并到秩较大的树中,以保证新树的秩不大于任何一棵原始树。如果r1和r2相等,两棵树任意合并,新树的秩为R1 ^ 1。

代码:

1 int find(int x)

2 {

3 if(x==parent[x])

4 {

5返回x;

6 }

7其他

8 {

9 parent[x]=find(parent[x]);

10返回find(parent[x]);

11 }

12 }

13

14 void to_union(int x1,int x2)

15 {

16 int f1=find(x1);

17 int F2=find(x2);

18 if(秩[f1]秩[f2])

19 {

20亲本[F2]=f1;

21 }

其他22个

23 {

24亲本[f1]=F2;

25 if(秩[f1]==秩[f2])

26 {

27秩[F2];

28 }

29 }

30 }

今天到此为止吧。

拜拜。

Link to comment
Share on other sites