并查集大致讲解
开始时每个集合都是一个独立的集合,并且都是等于自己本身下标的数
例如:
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
#include<iostream>
using namespace std;
const int N=100010;
int p[N];//定义多个集合
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
/*
经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
p[x]=x;
*/
return p[x];
//找到了便返回祖宗节点的值
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(*op=='M') p[find(a)]=find(b);//集合合并操作
else
if(find(a)==find(b))
//如果祖宗节点一样,就输出yes
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
find 函数不仅有找祖宗的功能，还把这个查找路径上所有节点直接变成了祖宗节点的孩子
这就相当于路径压缩了
不是相当于，这就是路径压缩
为什么find()里面是if不是while啊
俺也想知道
我的理解是，y总视频里画的，找到了祖宗节点之后，直接指向祖宗节点（就是路径压缩）,他不需要遍历，因为你输入的a和b，就只find(a)找a的祖宗节点，find(b)找b的祖宗节点。
感觉这是递归啊，如果还没找到就会找下一层
递归啦
我也想了这个问题，感觉应该是递归调用了，所以不需要采用while了
因为是递归，会一直往下深入直到找到祖宗节点，再一层层往上传
我的理解是p[x]=find(p[x])，直到找到它的祖宗节点，之后返回祖宗节点的值，每个节点的父节点的值都会变成祖宗节点的值，至此实现了路径压缩
没错,就是这样
666
如果还有不理解的，建议看这篇https://www.acwing.com/solution/content/33345/
大佬，p[a] = find(p[a])不是表示将a的父节点指向a的父节点的祖宗节点吗？那到最后会不会把a的父节点以上的数都指向祖宗节点了，而a还没有指向祖宗节点？
p[a]的意思,是a指向的父节点,最初始的就是p[a]=a,意思就是a指向的父节点是a
而find(p[a])就是a的祖宗节点的意思,所有a最终还是会指向祖宗节点的
明白了，谢谢大佬
既然p[a]=a,那我写p[a]=find[a]咋不行
最初始的时候是相等的，但是你查找的时候不是初始状态，这个时候查找p[a]就是等于find[a]会陷入循环
一开始p[a]也可能不是指向a，合并操作之后a的父节点就会改变
然后再进行find操作，此时p[a]就不等于a了
p[a]的意思就是a的父节点,而find(p[a])操作是找到a的父节点的祖宗,
然后将a的父节点的祖宗赋给a的父节点,所以此时a指向a的祖宗节点
为什么op要定义成op[2]，而不是直接写op;
都可以吧
写op[2]就是读入字符串，可以规避掉意料之外的输入，如空格之类的
OO
难道不是为了在字符串末尾加上一个\0?
y总上课说如果只写op白板容易读入空格回车之类，用串的话会自动忽略
ORZ
为什么原题案例中的第二个输出No??
你没初始化P[i]
刚刚开始有点疑惑为什么每次find的时候只对当前查询的元素改变值，比如说{4,6,7,10}，以6为祖宗节点，按道理将其与{3,5}合并之后，我们不但要修改6的值，还需要修改4710，后面发现假如说后面的询问{3,5}与4是否在一个集合，p[4]是可以查找到祖宗节点，是可以知道在一个集合里面的！
但是如果这样写并查集，那是不是就只能操作数组下标范围的元素，如果数组下标从0到100，那是不是只能合并查找0到100这些数字，那如果想要使用并查集操作字符串，或者操作非常离散的数字，是不是就得使用离散化了
其实一直没看懂find函数，到底怎么理解啊？我知道find函数是找到祖宗节点，但是是怎么找到的有大佬解释一下过程吗？定义在外面的int p[N]初值不都是0吗，然后find函数里面递归是怎么递归的啊？
抱歉 傻了 有for(int i=1;i<=n;i++) p[i]=i;
太好了 这下全都理解了。教训：一点小东西忽略了就会造成大的误解。
哈哈，这个教训以后会一直体会到的
为什么用string定义要输入的字符会报错？用char op[2]就不报错了
while(m–)
{
string op;
cin>>op;
int a,b;
scanf(“%d%d”,&a,&b);
if(op==”M”) p[find(a)]=find(b);//集合合并操作
else
if(find(a)==find(b))
//如果祖宗节点一样,就输出yes
printf(“Yes\n”);
else
printf(“No\n”);
}
string 要用cin，scanf的话好像类型可能会弄错
int n,m;
scanf(“%d%d “,&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
while(m–)
{
char op;
int a,b;
scanf(“%c %d %d “,&op,&a,&b);
if(op==’M’) p[find(a)]=find(b);//集合合并操作
else
if(find(a)==find(b))
//如果祖宗节点一样,就输出yes
printf(“Yes\n”);
else
printf(“No\n”);
}
return 0;
这是char的版本,输入前后要加空格
懂了懂了，谢谢大佬
为什么我使用%c会出错，它读不完全
注意加空格,这个是scanf的特性
ok，懂了谢谢大佬
int find(int x)
{
if(p[x]!=x) return find(p[x]);
return p[x];
}
大佬们，为什么这样写会超时？
光return find(p[x])的话,没有将集合合并,return p[x]=find(p[x])会将x这个点的集合改变成要合并的集合
没有修改px的值，你每一次寻找都要重新顺藤摸瓜往上去找他的很多个祖宗直到找到顶，px = findpx实际上就是让他辈分加一了，找到祖宗后他就是祖宗下面的那一代，实现了路径压缩，下次寻找他的祖宗之需要o1的时间
感觉这里的操作就像是一条单链表，每个节点再合并时都指向头节点，当然用树也可以这么理解，单链表本就是一棵特殊的树
感觉自己学懵了要，如果p[x]就是祖宗节点为什么不直接return p[x],要用递归啊
p[]存储的是x的父节点，祖宗节点是找不到父节点时，祖宗点初始化为p[i] = i;理解不了主要是在于这里的x是不断更新的
这是递推
##牛
太强了
find（x）函数找x的祖宗结点
重要的是p[x]的值，存的是当前所在集合的祖宗结点,当p[x]=x,表示这个数就是祖宗结点
你把两个不同集合中的两个数a，b传给分别find，返回的是两个集合的祖宗结点值，要是令两者合并让一个p【祖宗结点】=另外一个祖宗结点的值，两个集合就合并了，你可以想象原来的集合一个数在find找它的祖宗结点，找到原来的祖宗结点，此时它的p[x]!=x,代表他不是祖宗结点了，还会继续往下面找，直到找到它现在的祖宗结点为止
非常不错，加油！
# 很清晰
我懂了