d[n]代表了我距离最开始的一个根节点的距离。在维护并查集时,同时也需要维护并查集的距离,那么如何代表该物种吃与不被吃呢?
用该节点到当前节点的距离表示,由于有且仅有三个物种,可以利用对3取模判断,当结果为1时表示有吃和被吃关系,结果为0时表示为同类,同时由于我们利用并查集维护了距离,所以查询速度为$O(1)$,算法时间复杂度为$O(N)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50100;
int p[N], d[N];
int find(int n){
if(p[n] != n){
int root = find(p[n]);
d[n] += d[p[n]];
p[n] = root;
}
return p[n];
}
int main()
{
int _, n;
cin >> _ >> n;
for(int i = 0;i <= _; i ++)
p[i] = i;
int ans = 0;
while(n --){
int a, b, c;
cin >> a >> b >> c;
if(b > _ || c > _){ ans ++;continue;}
else if(a == 2 && b == c){ans ++;continue;}
int xx = find(b), yy = find(c);
int dis;
if(a == 2) dis = 1;else dis = 0;
if(xx == yy){
if( ( ( (d[b] - d[c]) % 3) + 3) % 3 != dis)
ans ++;
}else{
p[xx] = yy;
d[xx] += d[c] - (d[b] - dis);
}
}
cout << ans;
}