C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int p[N], d[N];//d[x]表示:x到父节点的距离(经路径压缩后才为到root的距离)
int find(int x)
{
if (p[x] != x)
{
int t = p[x];
p[x] = find(p[x]);
d[x] += d[t];//经过路径压缩后,p[t]一定为root,因此d[t]表示为父节点到root的距离
}
return p[x];
}
int main()
{
int res = 0;
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++)p[i] = i;
while (k--)
{
int D, x, y; cin >> D >> x >> y;
int px = find(x), py = find(y);
if (x > n || y > n) { res++; continue; }
if (D == 2 && x == y) { res++; continue; }//不加continue就会多计数
if (px != py)
{
if (D == 1)//同类合并
{
d[px] += d[y] - d[x];
p[px] = py;
}
else if (D == 2)//捕食合并
{
d[px] += -1 + d[y] - d[x];
p[px] = py;
}
}
else
{
if (D == 1 && (d[x] - d[y]) % 3 != 0)res++;
if (D == 2 && (d[x] + 1 - d[y]) % 3 != 0)res++;
}
}
cout << res;
}