题目大意就是给N个虫子，K个交配关系，问这K个交配关系中有没有同性恋，重口味啊～
首先，如果两个虫子中有一个虫子是以前从来没有处理过的，那么两个虫子就可以合并到一个集合里面，而且这两个虫子一定是异性，如果两个虫子都处理过了，那就在集合之中各种查找就行，看看两只虫子到底是异性还是同性，而我们知道了集合中各种虫子的关系，加以区分就可以了。那么小弟我今天刚刚学会并查集向量偏移这个思想，就稍稍的推一下哈～
首先，假定两只虫子的是异性的时候，偏移量为1，同性的时候，偏移量为0，毋庸置疑，初始化并查集的时候由于所有虫子的根节点都是它们本身，那么所有虫子的偏移量都是0。下面我们来考虑一下向量的多边形定则，如果是一个四边性，有四个顶点A，B，C，D，那么向量A→D=A→B+B→C+C→D，那么我们合并集合的时候就完全可以借鉴这种多边形定则的思想，把两个元素之间的关系看成是一个向量，推导出来公式加一下下就可以啦～不过要注意方向啊。
下面附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