很经典的一道关系型并查集题目
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
#define MAX 50001
int father[MAX],rank[MAX];
void _Set(int x){
for(int i = 1;i <= x;i++){
father[i] = i;
rank[i] = 0;
}
}
int _Find(int x){
int y,temp,dis,len;
y = x,len = 0;
while(y != father[y]){
len = (len + rank[y]) % 3;
y = father[y];
}
while(x != father[x]){
temp = father[x];
dis = rank[x];
rank[x] = len % 3;
father[x] = y;
len =(len - dis + 3) % 3;
x = temp;
}
return y;
}
void _Union(int x,int y,int d){
int xx = _Find(x);
int yy = _Find(y);
int len = d - 1;
father[yy] = xx;
rank[yy] = (rank[x] - rank[y] + len + 3) % 3;
}
int main(){
int n,k,d,x,y;
scanf("%d%d",&n,&k);
_Set(n);
int sum = 0;
for(int i =0;i < k;i++){
scanf("%d%d%d",&d,&x,&y);
if(x > n || y > n || ( d == 2 && x == y)){
sum++;
continue;
}
int rx = _Find(x);
int ry = _Find(y);
if(rx == ry){
if(d == 1 && rank[x] != rank[y]){
sum++;
continue;
}
if(d == 2 && (3 - rank[x] + rank[y] ) % 3 != d - 1){
sum++;
continue;
}
}
else _Union(x,y,d);
}
printf("%d\n",sum);
return 0;
}