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