題目大意就是給N個(gè)蟲子，K個(gè)交配關(guān)系，問這K個(gè)交配關(guān)系中有沒有同性戀，重口味啊～
首先，如果兩個(gè)蟲子中有一個(gè)蟲子是以前從來沒有處理過的，那么兩個(gè)蟲子就可以合并到一個(gè)集合里面，而且這兩個(gè)蟲子一定是異性，如果兩個(gè)蟲子都處理過了，那就在集合之中各種查找就行，看看兩只蟲子到底是異性還是同性，而我們知道了集合中各種蟲子的關(guān)系，加以區(qū)分就可以了。那么小弟我今天剛剛學(xué)會并查集向量偏移這個(gè)思想，就稍稍的推一下哈～
首先，假定兩只蟲子的是異性的時(shí)候，偏移量為1，同性的時(shí)候，偏移量為0，毋庸置疑，初始化并查集的時(shí)候由于所有蟲子的根節(jié)點(diǎn)都是它們本身，那么所有蟲子的偏移量都是0。下面我們來考慮一下向量的多邊形定則，如果是一個(gè)四邊性，有四個(gè)頂點(diǎn)A，B，C，D，那么向量A→D=A→B+B→C+C→D，那么我們合并集合的時(shí)候就完全可以借鑒這種多邊形定則的思想，把兩個(gè)元素之間的關(guān)系看成是一個(gè)向量，推導(dǎo)出來公式加一下下就可以啦～不過要注意方向啊。
下面附AC代碼
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define N 2010
9 struct data
10 {
11 int p, r;
12 }p[N];
13 int find(int x)
14 {
15 int temp;
16 if (p[x].p == x) return x;
17 temp = p[x].p;
18 p[x].p = find(temp);
19 p[x].r = (p[x].r + p[temp].r) % 2;
20 return p[x].p;
21 }
22 int main()
23 {
24 int t;
25 int n, k;
26 int x, y;
27 int r1, r2;
28 bool ju;
29 cin >> t;
30 for (int j = 1; j <= t; j++)
31 {
32 ju = 0;
33 cin >> n >> k;
34 for (int i = 1; i <= n; i++)
35 {
36 p[i].p = i;
37 p[i].r = 0;
38 }
39 for (int i = 0; i < k; i++)
40 {
41 scanf("%d%d", &x, &y);
42 r1 = find(x); r2 = find(y);
43 if (r1 != r2)
44 {
45 p[r2].p = r1;
46 p[r2].r = (1 + p[x].r - p[y].r) % 2;
47 }
48 else
49 {
50 if (((2 - p[x].r + p[y].r) % 2) != 1)
51 ju = 1;
52 }
53 }
54 printf("Scenario #%d:\n", j);
55 if (ju) cout << "Suspicious bugs found!" << endl << endl;
56 else cout << "No suspicious bugs found!" << endl << endl;
57 }
58 return 0;
59 }
60