AcWing 240. 食物链
原题链接
中等
作者:
CCabout
,
2020-11-08 22:11:56
,
所有人可见
,
阅读 431
240.食物链(维护到祖宗节点距离的并查集)
思路
p[i] :i到祖宗节点的距离
取模3 余数1--可以吃根节点
余数2--可以被根节点吃
余数0--与根节点为同类
c++代码
#include<iostream>
using namespace std;
const int N=50010;
int p[N],d[N];
//并查集核心操作
int find(int x){
if(p[x]!=x){
int u=find(p[x]);
d[x]+=d[p[x]];
p[x]=u;
}
return p[x];
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)p[i]=i;
int count=0;
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){//x和y是同类
if(px==py && (d[x]-d[y])%3)count++;
else if(px!=py){
p[px]=py;//不妨把py作为根节点
d[px]=d[y]-d[x];//x和y是同类,到根节点py的距离应该相等,
//即(dx+?-dy)%3==0 所以?=dy-dx,,,?为d[p[x]]
}
}
else{
1.
if(px==py && (d[x]-d[y]-1)%3)count++;
else if(px!=py){
p[px]=py;
d[px]=d[y]+1-d[x];
}
}
}
}
cout<<count<<endl;
return 0;
}