开始时每个集合都是一个独立的集合,并且都是等于自己本身下标的数
例如:
p[5]=5,p[3]=3;
如果是M操作的话那么就将集合进行合并,合并的操作是:
p[3]=p[5]=5;
所以3的祖宗节点便成为了5
此时以5为祖宗节点的集合为{5,3}
如果要将p[9]=9插入到p[3]当中,应该找到3的祖宗节点,
然后再把p[9]=9插入其中,所以p[9]=find(3);(find()函数用于查找祖宗节点)
也可以是p[find(9)]=find(3),因为9的节点本身就是9
此时以5为祖宗节点的集合为{5,3,9};
如果碰到多个数的集合插入另一个集合当中其原理是相同的
例如:
上述中以5为祖宗节点的是p[5],p[3],p[9];(即p[5]=5,p[3]=5,p[9]=5)
再构造一个以6为祖宗节点的集合为{6,4,7,10}
如果要将以6为祖宗节点的集合插入到以5为祖宗节点的集合,则该操作可以是
p[6]=find(3)(或者find(9),find(5))
此时p[6]=5
当然如果是以6为祖宗节点集合中的4,7,10则可以这样
p[find(4)]=find(3)
或者p[find(7)]=find(3)均可以
此时以6为祖宗节点的集合的祖宗节点都成为了5
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;//表示这个数组的最大长度
int p[N];//用来存储每一个结点的父亲结点
int n, m;
int find(int x)
{
if (p[x] != x)
{
p[x] = find(p[x]);
}
return p[x];
}
int main()
{
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; i++)
{
p[i] = i;//开始每个结点的父亲节点的为他自己
}
while (m--)
{
char s[2];
int a, b;
scanf("%s%d%d", s, &a, &b);
if (s[0] == 'M')
{
p[find(a)] = find(b);
}
else if (s[0] == 'Q')
{
if (find(a) == find(b))
puts("Yes");
else
puts("No");
}
}
return 0;
}