AcWing 240. 食物链
原题链接
中等
作者:
Naive_512
,
2022-01-26 15:49:37
,
所有人可见
,
阅读 139
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int father[N],deep[N];
int n,m;
int find(int x)
{
if(father[x]!=x)
{
int tmp = find(father[x]);
deep[x] += deep[father[x]];
father[x] = tmp;
}
return father[x];
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++) father[i] = i;
int ans = 0;
while(m --)
{
int z,x,y;
cin >> z >> x >> y;
int a = find(x),b = find(y);
if(x > n || y > n) ans++;
else
{
if(z == 1)
{
if(a == b && (deep[x] - deep[y]) % 3) ans ++;
else if(a != b)
{
father[a] = b;
deep[a] = deep[y] - deep[x];
}
}
else
{
if(a == b && (deep[x] - deep[y] - 1) % 3) ans ++;
else if(a != b)
{
father[a] = b;
deep[a] = deep[y] - deep[x] + 1;
}
}
}
}
cout << ans;
return 0;
}