并查集的原理+例题
并查集的原理+例题
- 1. 并查集原理
- 2. 例题
- 基础实验4-2.8 部落
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 f(int a)
{
if (pre[a] != a) pre[a] = f(pre[a]);
return pre[a];
}
注意:这是一个递归函数,递归 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 的圈子里了
代码如下:
void merge(int father, int child)
{
int mm = father, nn = child;
if (f(father) != father)
mm = f(father);
if (f(father) != child)
nn = f(child);
pre[nn] = mm;
}
int f(int a)
{
if (pre[a] != a) pre[a] = f(pre[a]);
return pre[a];
}
到此为止,我们就完成了并查集的原理代码
2. 例题
基础实验4-2.8 部落
原题链接
#include<iostream>
using namespace std;
int pre[10001], e[10001];
int f(int a)
{
if (pre[a] != a) pre[a] = f(pre[a]);
return pre[a];
}
void merge(int father, int child)
{
int mm = father, nn = child;
if (f(father) != father)
mm = f(father);
if (f(father) != child)
nn = f(child);
pre[nn] = mm;
}
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) <<endl;
}
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;
}