AcWing 240. 食物链
原题链接
中等
作者:
术
,
2021-01-08 13:26:30
,
所有人可见
,
阅读 333
#include <iostream>
using namespace std;
const int N=100005;
int p[N];
int d[N];//表示到p[x]的距离
int find(int x){
if(x!=p[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 res=0;
while(k--){
int op,x,y;
cin>>op>>x>>y;
if(x>n||y>n) {
res++;
continue;
}
if(op==1){
int px=find(x),py=find(y);
//通过与根节点的距离判断属于哪一类,若同根结点,则说明已经分配
if(px==py&&(d[x]-d[y])%3!=0){
res++;
}
else if(px!=py){//未分配类,则合并两个集合
p[px]=py;
d[px]=d[y]-d[x];//
}
}
else{
if(x==y) {
res++;
continue;
}
int px=find(x),py=find(y);
if(px==py&&(d[x]-d[y]-1)%3!=0) res++;
else if(px!=py){
p[px]=py;
d[px]=d[y]-d[x]+1;
}
}
}
cout<<res;
//cout << "Hello world!" << endl;
return 0;
}
哇塞