因为我们一共有三个群体，所以我们可以开三倍的并查集，$1$~$n$的部分表示为A的群体，$n+1$~$2n$的部分表示B的群体，$2n+1$~$3n$的部分表示C的群体
题干给的三种关系，A吃B，B吃C，C吃A
我们可以由二倍并查集，由特殊到一般，由二到三，在二倍并查集中：当A中的x与B中的y合并，有关系x吃y，当C中的x与C中的y合并，有关系x和y是同类。那么在三倍并查集中就有这样的几种关系：
udpate(x,y) | update(x+n,y+n) | update(x+n+n,y+n+n)表示着同类合并
find(x)==find(y+n)表示x吃y同理可得剩下的情况（主要是因为我懒）
1 #include <iostream>
2 #include <algorithm>
3 #include <cstdio>
4 using namespace std;
5 int n,k;
6 const int maxn=1e5+10;
7 int mark,x,y;
8 int ans,fa[3*maxn];
9 void init(){
10 for (int i = 1;i <= n*3;i++) fa[i]=i;
11 }
12 int find(int x){
13 if (fa[x]==x) return x;
14 else return fa[x]=find(fa[x]);
15 }
16 void update(int x,int y){
17 int fx=find(x),fy=find(y);
18 fa[fx]=fy;
19 }
20 int main(){
21 scanf("%d%d",&n,&k);
22 init();
23 for (int i = 1;i <= k;i++){
24 scanf ("%d%d%d",&mark,&x,&y);
25 if (x>n||y>n){ans++; continue;}
26 if (mark==1){
27 if (find(x)==find(y+n)||find(x+n)==find(y)) ans++;
28 else {
29 update(x,y);
30 update(x+n,y+n);
31 update(x+n+n,y+n+n);
32 }
33 }
34 else{
35 if (find(x)==find(y)||find(x+n)==find(y)) ans++;
36 else {
37 update(x,y+n);
38 update(x+n,y+n+n);
39 update(x+n+n,y);
40 }
41 }
42 }
43 printf("%d
",ans);
44 return 0;
45 }