并查集的原理+例题

1. 并查集原理

如图，在三个圈中，分别有数字
1 2 3 4
4 6 7 8
11 12

我们规定，每个圈中都有自己的大佬，并且只有1个
所以，
2 3 4 跟随的就是1
6 7 8 跟随的就是4
12 跟随的就是 11

但是我们发现，4在圈1中也出现了，那么既然4在圈1中跟随的是 数字1
那么所以 6 7 8也就跟随的是 数字1

既然如此了，那么图中，其实就只剩 两个圈了，
并查集的作用就是 把 2 3 4 6 7 8 都跟随到 数字1
12跟随到 数字11

那么怎么做到 当我们得到数字 2 3 4 6 7 8就能得到 他们的大佬数字 1呢？

方法如下：

我们定义一个数组，使角标为 2 3 4 5 6 7 8的数组值 都为 1
这样我们就能得到他们的大佬是 1.

但是，最开始的时候

6 7 8的大哥其实是 4
那么我们怎么 使得 6 7 8的大哥改成为1的呢
其实那么我就把 6 7 8的大哥拿出来，看一看，大哥的数组值是不是自己的角标，如果是，那么说明大哥没有大哥的大哥，也就是大哥把自己作为大哥，那么怎么拿出大哥的数组值呢？

我们把整个数组名 记作 a
那么 角标6的大哥 的角标也就是 a[6]（也就是4） 那么a[a[6]] 就表示6的大哥角标，我们判断 大哥的角标是否等于 自身值 a[a[6]] 4，如果不等于，那么我们再去找 a【a[a[6]]】即可。

综上就是这样一个代码

模板

int find(int x){
	if(fa[x]==x) return x;
	return  find(fa[x]);
}
int Union(int x,int y){
	int rx = find(x),ry=find(y);
	if(rx!=ry) fa[ry]=rx;
} 
1
2
3
4
5
6
7
8

注意：这是一个递归函数，递归 pre[a] = f(pre[a]);

补充讲解一下：递归函数，什么叫做递归函数
递：就是可以一直往下传递（也就是自己调用自己 如f(pre[a])）
归：就是返回值，有接收 pre[a] = f(pre[a])（这样才能有良性的递归）
如果 我们只写成 f(pre[a]) 那么这个函数的返回值，没有数据进行接收，则不能真正递归

当我们已经会找到一个数据的老大了，那么我们还需要把两个数据归并到一个老大中，比如a，b
我们要把b归并到a的圈子里，怎么做呢？
其实我们只需要找到a的老大，或者a本身就是老大
然后 我们找到b的老大，或者b就是自己的老大
最后 我们让 b的老大 等于 a的老大
这样一来，我们就把b的圈子 全部 归到 a 的圈子里了
代码如下：

int find(int x){
	if(fa[x]==x) return x;
	return  find(fa[x]);
}
int Union(int x,int y){
	int rx = find(x),ry=find(y);
	if(rx!=ry) fa[ry]=rx;
} 
1
2
3
4
5
6
7
8

到此为止，我们就完成了并查集的原理代码

2. 例题

基础实验4-2.8 部落

原题链接

#include
using namespace std;

int pre[10001], e[10001];

int f(int x){
	if(fa[x]==x) return x;
	return  f(fa[x]);
}
int merge(int x,int y){
	int rx = find(x),ry=find(y);
	if(rx!=ry) fa[ry]=rx;
} 

int main()
{
    for (int i = 1; i <= 10001; i++)
        pre[i] = i;
    int max = 0;
    int N;
    cin >> N;
    while (N--)
    {
        int n;
        cin >> n;
        int p = 0, q = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i == 1)
            {
                cin >> q;
                if (q > max) max = q;
            }
            else
            {
                cin >> p;
                if (p > max) max = p;
                merge(q, p);
                q = p;
            }
        }
    }

    for (int i = 1; i <= max; i++)
    {
        e[f(i)]++;
    }
    int g = 0;
    for (int i = 1; i <= max; i++)
    {
        if (e[i])
            g++;
        //cout << f(i) <
    }
 cout << max << ' ' << g << endl;
    int q,p;        
   cin >> N;
    while(N--)
    {
        
         cin >> q >> p;
         if(f(p) == f(q))
            cout << 'Y' << endl;
        else
             cout << 'N' << endl;
     }
  
    return 0;
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69