AcWing 240. 食物链
原题链接
中等
作者:
stc
,
2024-02-05 21:08:01
,
所有人可见
,
阅读 27
C++ 代码
/*食物链(带边权并查集)*/
#include <iostream>
using namespace std;
const int N = 50010;
int n,m;
int p[N],d[N];
int find(int x){
if(p[x] == x) return x;
int rx = find(p[x]);
d[x] += d[p[x]];
return p[x] = rx;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) p[i] = i, d[i] = 0;
int res = 0;
while(m--){
int t, x, y;
cin>>t>>x>>y;
if(x > n || y> n) {
res ++;
continue;
}
int rx = find(x),ry = find(y);
if(t == 1){
if(rx == ry && (d[x]-d[y])%3) res ++;
else if(rx != ry){
p[rx] = ry;
d[rx] = d[y] - d[x]; // (d[x]+d[px]-d[y])%3==0
}
}
else{
if(rx == ry && (d[x]-d[y]-1)%3) res ++;
else if(rx != ry){
p[rx] = ry;
d[rx] = d[y] - d[x] + 1; // (d[x]+d[px]-d[y]-1)%3==0
}
}
}
cout<<res<<endl;
return 0;
}