AcWing 240. 食物链
原题链接
中等
作者:
史一帆
,
2022-01-02 16:08:17
,
所有人可见
,
阅读 186
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 10;
int p[N], d[N];// d[i]:第i个动物在食物链中的深度
int find(int x)
{
int fx = p[x];
if (x != p[x])
{
p[x] = find(p[x]);
d[x] = (d[x] + d[fx]) % 3;
}
return p[x];
}
int main()
{
int n, k;
cin >> n >> k;
int res = 0;
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
while (k -- )
{
int c, x, y;
cin >> c >> x >> y;
if (x > n || y > n || (c == 2 && x == y))
{
res ++ ;
continue;
}
int fa = find(x), fb = find(y);
if (fa == fb)
{
if ((d[x] - d[y] + 3) % 3 != c - 1)
res ++ ;
}
else
{
p[fa] = fb;
d[fa] = (d[y] - d[x] + c - 1 + 3) % 3;
}
}
cout << res << endl;
return 0;
}