【并查集】食物链

并查集

题目传送门：CodeVS1074

现在才发现我这么蒟蒻，并查集都不怎么会用啊！！！

这道题似乎用了一个很巧妙（估计是我太弱）的东西，就是用 i , i+n , i+n*2 来表示 i 在 A B C 三个种类，似乎是可以轮换的

然后每读入一次先验证是否是假话，不是的话就合并（好像是废话）

具体见代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
int fa[150005],n,m,x,y,z,ans;
int find(int x){
	if (fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
void unite(int x,int y){
	x=find(x);
	y=find(y);
	if (x==y) return;
	fa[x]=y;
}
int main(){
	cin>>n>>m;
	
	for (int i=1;i<=n*3;i++)
		fa[i]=i;
	for (int i=1;i<=m;i++){
		cin>>z>>x>>y;
		
		if (x<0 || x>n || y<0 ||y>n){
			ans++;
			continue;
		}
		
		if (z==1){
			if (find(x)==find(y+n) || find(x)==find(y+n*2)){//x与y一样时显然不能互相吃来吃去
				ans++;
				continue;
			}
			else{
				unite(x,y);
				unite(x+n,y+n);
				unite(x+n*2,y+n*2);
			}
		}
		
		if (z==2){
			if (find(x)==find(y) || find(x)==find(y+n*2)){//x吃y时x显然不与y一样，也不能是y吃x
				ans++;
				continue;
			}
			else{
				unite(x,y+n);
				unite(x+n,y+n*2);
				unite(x+n*2,y);
			}
		}
	}
	
	cout<<ans;
}