并查集_找爹法选择题

并查集(找爹算法)

定义

并查集是一种树形的数据结构，由两部分组成：

• 合并（Union）：把两个不相交的集合合并为一个集合。
• 查询（Find）：查询两个元素是否在同一个集合中。

算法概述

用集合中的某个元素来代表这个集合，该元素称为集合的代表元。

一个集合内的所有元素组织成一代表元为根的树形结构。

合并：对于每个元素tr[x]指向x所在树形结构上的父节点。如果x就是根节点，则tr[x] = x;

查询：假设需要确定x所在的集合，也就是确定集合的代表元，可以沿着tr[x]不断的在树形结构中向上移动，直到达到根节点。

判断两个元素是否属于同一个元素，只需要看他们的代表元是否相同即可。

三个操作

先来举一个例子，帮助理解……

快过年了，犯罪分子也开始为年终奖“努力奋斗”了。犯罪分子有不同的团伙，警车叔叔想弄清楚到底有多少个犯罪团伙，他手中收集到一些线索，让你帮忙分析一下。

现在一共有11个强盗。

1号与2号是同伙。

3号与4号是同伙。

5号与2号是同伙。

4号与6号是同伙。

2号与6号是同伙。

7号与11号是同伙。

8号与7号是同伙。

9号与7号是同伙。

9号与11号是同伙。

1号与6号是同伙。

需要注意强盗的强盗也是同伙。

要想解决这个问题，我们可以先假设每个强盗各自为政，每个人都是自己的首领

第一步：初始化

先申请一个一维数组tr，用来储存每个强盗的首领是谁。

然后给让tr[i] = i；初始化

然后根据警方的线索将两个盗贼连接起来(具体的看下面)

第二步：寻找首领

即find()函数，用来找根节点

第三步：合并同伙

就是如果发现目前两个强盗是同伙，则这两个强盗是同一个犯罪团队，然后合并他们

那么合并之后谁是这个犯罪团队的首领BOSS呢？具体是怎么操作的呢？什么是压缩了件

看警方的第一条线索：1号与2号是同伙，这两个强盗的BOSS本身都是自己，现在变成一个犯罪团伙，我们就要确定一个BOSS，无论选1还是选2都是一样的，古代以左为尊，那我们就用“靠左”法则吧，就让1是BOSS，让tr[2] = 1;这样2的BOSS是1了

第二条线索是：3与4是同伙，同样的，我们让tr[4] = 3；即4的BOSS是3.

第三条线索是：5与2是同伙，这个时候，我们看tr[2] = 1,不是2，而tr[5] = 5，如果我们把tr[2] = 5，那么盗贼1肯定就不乐意了，“你怎么能抢老子的人”,为了避免他们掐架，我们可以用和平一点的方法解决问题，让1的BOSS是5，这样就形成一个树，可以顺着树爬上去，找到根节点，而且树上的成员都是一个团队的了，所以tr[1] = 5；

第四条线索：4号和6号是同伙，我们知道四号的BOSS是3号，根据靠左原则，我们就可以让tr[6] = 3

第五条线索是：2号和6号是同伙，我们知道2号的BOSS是5，6号的BOSS是3，根据擒贼先擒王和靠左原则，我们对两个树进行合并，就是让tr[3] = 5, 同时，我们可以进行一次路径压缩，tr[2] = 5,也就是说，2也变成了BOSS5的直属下司。这就是强盗团伙的江湖规矩，谁能找到自己帮派的大BOSS，就会被提拔成直属下司。这种扁平化的管理能有效提高强盗团伙找大BOSS的效率，这就叫做“路径压缩”。

其实你也可以不用路径压缩，但是这样就会让树的深度很大，你要通过递归的方式进行查找，就会很费时，如果是在比赛，一发TLE你就懵了。一会我会把不进行路径压缩的代码，以及三种不同的路径压缩的代码写上去

第六条线索是:7号与11号，根据靠左原则，让tr[11] = 7，构建出一个新的树

第七条线索是：8号与7号，根据靠左原则，让7号归顺8号，即tr[7] = 8,

第八条线索是：9号与7号，根据靠左原则，和擒贼先擒王原则，让7号的BOSS8号归顺9号，即tr[8] = 9;

第九条线索是：9与11，tr[9] = 9, tr[11] = 7,两者的BOSS并不同，但是很显然，图上画着二者是一个团队，说明11号并不是直属与大BOSS9号，我们就又可以进行路径压缩，我们来模拟一遍，首先11号归顺于7号，7号归顺于8号，8号归顺于9号，tr[9] = 9，说明9号就大BOSS，太棒了，根据江湖规矩，能找到自己大BOSS的就能被大BOSS直接提拔成直属下司！

第十条线索是：1号和6号，tr[1] = 5,而tr[6] = 3,二者又在同一个队伍，当6顺着藤摸上去找他的BOSS时，找到了5，和1是一样的，而根据江湖规矩，6成了BOOS5的直属下司，tr[6] = 5，有一点需要注意的是，路径压缩只能顺着一条藤摸过去，只能将这条藤上的瓜嫁接到大BOOS上，而不能干涉其他藤上的瓜，就像4，不在6-3-5这个藤上，所以就不能嫁接到大BOSS上

所有的线索分析完毕，那么究竟有多少个犯罪团伙呢？我们只需要遍历一遍tr[]数组，看看里面的元素有多少个是满足tr[i] = i，有几个就有几个犯罪团伙，一遍历，发现有三个。

我们刚刚手动模拟的过程其实就是并查集的算法。通过一个一维数组实现的，其本质就是在不停的找爹，然后认爹，在认爹的过程格外要注意遵守靠左原则和擒贼先擒王原则

代码实现

初始化

int n;
int tr[10005];
void init ()
{
    for(int i = 0; i < n; i++)
        tr[i] = i;
}
1
2
3
4
5
6
7

找爹函数—tfind()

int tfind(int x)
{
    if(tr[x] == x)
        return x;
    else
    {
        tr[x] = tfind(tr[x])//这就是路径压缩,每次在函数返回的时候，顺带把路上遇到的人的BOSS改为最后找到的祖宗的编号，也就是犯罪同伙最高领导人的编号
        return tr[x];//这是返回的根节点
    }
}

1
2
3
4
5
6
7
8
9
10
11

int tfind(int x)//这是我看《啊哈算法》里面讲的，然后自己写的路径压缩代码，但是却来了发TLE，淦！用来帮助理解是可以的，要是拿去提交最好用上面那个代码……
{
    int j;
    int a;
    a=x;
    while(tr[a]!=a)///循环方法查找前导点，和上面那个代码一样，因为都得返回最后那个根节点
    {
        a = tr[a];
    }
    while(tr[x] != x)//路径“压缩”
    {
        j = x;//我把x的值给j储存
        x = tr[x];//因为tr[x] != x，我得找到那个tr[x] == x 的值才是根节点，所以继续找tr[tr[j]]，有些同学会问后两行为什么不可以写可做tr[j] = tr[tr[x]],那是因为这样你的x就没有改变，本来应该是x = tr[x],而你一步到位以后，x的值还是x，进行下一次循环就出问题了
        tr[j] = tr[x];//
    }
    return a;//这个是我们tfind函数最重要的返回值，返回根节点，不能丢了

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int tfind(int x)//这个是网上的，使用递归写find函数，同时有路径压缩，不过这个路径压缩也不靠谱，一样超时！
{
    int j;
    int a;
    a=x;
    while(tr[a]!=a)///循环方法查找前导点
    {
        a=tr[a];
    }
    int i=x,j;
    while(i!=a)///路径压缩
    {
        j=tr[i];///记录x的前导结点
        tr[i]=a;///将i的前导结点设置为r的根节点.
        i=j;
    }//和我写的差不多，但又有不同，比我的优化了点……
    return a;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int tfind(int x)
{
    while(tr[x] != x)//这个就没有路径压缩了，直接一步步顺着树找大BOSS，不知道为什么这个都不超时，我用路径压缩会超时！求大神指导
        x = tr[x];
    return x;
}
1
2
3
4
5
6

合并“树”

void tmerge(int a, int b)
{
    int x = tfind(a);//找到a的根节点，也就是a的大BOSS
    int y = tfind(b);//同样的找b的大BOSS，如果x == y,说明二者属于一个团队，不用合并，但是如果不相等，就根据靠左原则，进行树的合并
    if(x != y)
        tr[y] = x;
}
1
2
3
4
5
6
7

主函数

int main()
{
    int n, m, a, b;
    int sum = 0;//计有几个团队用
    cin>>n>>m;//输入n,代表有几个盗贼，输入m，代表有几条线索
    init();//初始化
    for(int i = 0; i < m; i++)
    {
        cin>>a>>b;//输入每个线索
        tmerge(a, b);
    }
    for(int i = 0; i < n; i++)
    {
        if(tr[i] == i)
            sum++;
    }
    cout<<sum<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

例题展示

oj水题

题意：

​ Company A has N employees, this company has lots of departments around the country. The employees who belong to different departments do not know each other, but if two employees are working in the same department they will know each other directly or indirectly (For example, 1 and 2 know each other directly,2 and 3 know each other directly, so 1 and 3 know each other indirectly, and they belong to the same department).
​ These N employees are numbered from 1 to N.

​ Now, giving you M informations about these N employees (two employees’ number, who knows each other directly).
If any people did not appear in the list of the M informations, these people belong to different departments.
Now, you should calculate how many departments this company has.

输入

​ The 1st line, N, ( 1<=N<=10000 ) the number of the employees belong to the company.
The 2ed line, M, ( 1<=M<=100000 ) the number of the informations about these N employees.
The next M lines, each line has two numbers, i and j, said that e mployee i and j knows each other directly.

输出

The maximum number of the departments that belong to company A.

题意：

简单来说就是一个公司有n个人，然后有m条关系，每条关系上的两人相互认识，而相互认识的人属于一个部门，最后让你输出一共有几个不同的部门

#include<bits/stdc++.h>
using namespace std;
int tr[10005];
int find1(int x)
{
    if(tr[x] == x)
        return x;
    if(tr[x] != x)
    {
        tr[x] = find1(tr[x]);
        return tr[x];
    }
}
int ran(int a, int b)
{
    int x = find1(a);
    int y = find1(b);
    if(x != y)
        tr[y] = x;
}
int main()
{
    int n, m, a, b;
    int sum = 0;
    cin>>n>>m;
    for(int i = 0; i < n ; i++)
    {
        tr[i] = i;
    }
    for(int i = 0; i < m; i++)
    {
        cin>>a>>b;
        ran(a, b);
    }
    for(int i = 0; i < n; i++)
    {
        if(tr[i] == i)
            sum++;
    }
    cout<<sum<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

小结

这个算法是在ICPC上海站之前学的，当时就没学透，稀里糊涂的就过了oj的1351题，也就是上面的那个题，之前想弄清楚它，但是在网上又没有真正的浅显易懂的讲解，然后还有一些奇奇怪怪的代码(就像上面那个路径压缩，那种做法明明比不压缩更耗时，但是某些博主也愣是发了出来)就导致我这篇文章耽误好久没写。直到上海站开始之前的那个早上，和队友聊谁负责什么算法的时候，知道了啊哈算法上也有并查集的讲解，然后我就在今天英语课上看了看，跟着书直接手推一遍，发现如此之简单，于是想这这篇文章的兴致突然就上来了，拦都拦不住。这次的文章可能写的比上次那个KMP还长，中间本来想弄个图床一个线索一个线索的上传照片，奈何本领不够，对于一些计算机网络知识不够了解，不能弄好图床，还耽误挺长时间(小小图床差点要走了我仅存的半条命！)