这道题是我学数据结构开始敲的第一道题，并查集，留作存目。这道题体现了一些问题，是我不知道的，也是我犯二了，竟然没想到过用类似于边权的东东来表示并查集中各个元素之间的关系的区别，不过还好了，现在转过来这个弯儿了。
这道题，所有的物种之间有三个关系，平等，吃与被吃，那么这三个关系可以分别用0,1,2来表示，如果遇到的两个生物从来没有处理过，或者说有一个没有处理过，那么这句话一定是跟前面的所有真话没有冲突的，如果这句话也没有违背剩下的两个条件，就可以把这个物种存进来，合并到一个集合中，并且关系给好好的设定一下，由于只有三个物种，而且三个物种之间的关系非常明确，我们就可以推导出来压缩路径的时候各个元素之间的关系的换算关系，所以呢～～～推导我也没弄明白……（- -||），如果遇到的两个物种全都处理过了，那么查找的时候必然是在同一个集合中，那就看它们的关系是否冲突就行了……如果它俩是同一个物种，那么它俩和根节点的关系一定就是一样一样的，如果不是同一个物种，换算公式啦……
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define M 50010
9 struct data
10 {
11 int p, r;
12 }p[M];
13 int find(int x)
14 {
15 int temp;
16 if (x == p[x].p) return x;
17 temp = p[x].p;
18 p[x].p = find(temp);
19 p[x].r = (p[x].r + p[temp].r) % 3;
20 return p[x].p;
21 }
22 int main()
23 {
24 int n, k;
25 int d, x, y;
26 int r1, r2;
27 int sum = 0;
28 cin >> n >> k;
29 for (int i = 1; i <= n; i++)
30 {
31 p[i].p = i;
32 p[i].r = 0;
33 }
34 for (int i = 0; i < k; i++)
35 {
36 scanf("%d%d%d", &d, &x, &y);
37 if (x > n || y > n)
38 {
39 sum++;
40 continue;
41 }
42 if (d == 2 && x == y)
43 {
44 sum++;
45 continue;
46 }
47 r1 = find(x); r2 = find(y);
48 if (r1 != r2)
49 {
50 p[r2].p = r1;
51 p[r2].r = (3 + (d - 1) + p[x].r - p[y].r) % 3;
52 }
53 else
54 {
55 if (d == 1 && p[x].r != p[y].r)
56 {
57 sum++;
58 continue;
59 }
60 if (d == 2 && ((3 - p[x].r + p[y].r) % 3 != (d - 1)))
61 {
62 sum++;
63 continue;
64 }
65 }
66 }
67 cout << sum << endl;
68 return 0;
69