這道題是我學數(shù)據(jù)結構開始敲的第一道題，并查集，留作存目。這道題體現(xiàn)了一些問題，是我不知道的，也是我犯二了，竟然沒想到過用類似于邊權的東東來表示并查集中各個元素之間的關系的區(qū)別，不過還好了，現(xiàn)在轉過來這個彎兒了。
這道題，所有的物種之間有三個關系，平等，吃與被吃，那么這三個關系可以分別用0,1,2來表示，如果遇到的兩個生物從來沒有處理過，或者說有一個沒有處理過，那么這句話一定是跟前面的所有真話沒有沖突的，如果這句話也沒有違背剩下的兩個條件，就可以把這個物種存進來，合并到一個集合中，并且關系給好好的設定一下，由于只有三個物種，而且三個物種之間的關系非常明確，我們就可以推導出來壓縮路徑的時候各個元素之間的關系的換算關系，所以呢～～～推導我也沒弄明白……（- -||），如果遇到的兩個物種全都處理過了，那么查找的時候必然是在同一個集合中，那就看它們的關系是否沖突就行了……如果它倆是同一個物種，那么它倆和根節(jié)點的關系一定就是一樣一樣的，如果不是同一個物種，換算公式啦……
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