AcWing 240. 解决几个小白疑惑的点
原题链接
中等
作者:
所念皆星河1
,
2023-01-11 13:59:37
,
所有人可见
,
阅读 175
经过思考后应该能理解下面这几点的
-
d[x]:x这个点到父节点,也就是p[x]的距离。如果我们让p[x]等于根节点,那d[x]就表示到根节点的距离
-
我们做这道题的时候不可避免会用箭头来表示谁吃谁,但是在本题并查集解法中这个箭头没有任何意义
该点到根节点的距离才是唯一评判标准,模3后这个点与根节点的关系就确定了
-
输入的点只要经历了find()函数,就会被调整,直接指向自身集合的根节点,同时d[x]也被修改了
-
两个不相交集合合并,说明两个根节点间的关系其实还没有确定,如果输入告诉我们这两个集合某两个点的关系
那么我们就可以假设这两个根节点的距离,将集合合并,通过这个距离,来使输入的就两个节点逻辑自洽
而在这个逻辑自洽的过程中,两个根节点距离确定,两个根节点的关系就确定了
至于find()函数,画一下图就明白了。不过这道题确实非常抽象,不是y总讲解可能题解都看不懂
C++ 代码
#include<iostream>
using namespace std;
const int N=50010;
int p[N],d[N],count;
int find(int x){
if(p[x]!=x){
int t=find(p[x]);//保存根节点下标
d[x]+=d[p[x]];//此时d[x]为到父节点的距离,d[p[x]也是到父节点的距离,只不过此时p[x]的父节点为t,也就是根节点
p[x]=t;//修改当前节点父节点为根节点
}
return p[x];
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;++i) p[i]=i;
while(k--){
int t,x,y;
cin>>t>>x>>y;
if(x>n||y>n) count++;
else{
int px=find(x),py=find(y);
if(t==1){
if(px==py&&(d[x]-d[y])%3) count++;
else if(px!=py){
p[px]=py;
d[px]=d[y]-d[x];
}
}else{
if(px==py&&(d[x]-d[y]-1)%3) count++;
else if(px!=py){
p[px]=py;
d[px]=d[y]-d[x]+1;
}
}
}
}
cout<<count;
return 0;
}