POJ 2492 A Bug's Life（带权并查集）

题目大意：有n只虫子，m对关系，m行每行有x y两个编号的虫子，告诉你每对x和y都为异性，先说的是对的，如果后面给出关系与前面的矛盾则说明有同性的虫子在，判断是否有两只同性虫子被放在一起。

解题思路：大概算是简化版的食物链吧，可以认为只有两个种类，雄性和雌性，给出x和y说明x->y的偏移值为1（因为是异性），只要维护好权值数组val[]就行了。如果x，y还没有关系就放入并查集中，有关系的话就判断是否为异性。

代码：

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cctype>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 #include<stack>
12 #include<string>
13 #define LC(a) (a<<1)
14 #define RC(a) (a<<1|1)
15 #define MID(a,b) ((a+b)>>1)
16 using namespace std;
17 typedef long long LL;
18 const int INF=0x3f3f3f3f;
19 const int N=2e3+5;
20 int val[N],root[N];
21 
22 int find(int x){
23     if(root[x]==x)
24         return x;
25     int tmp=find(root[x]);
26     val[x]=(val[x]+val[root[x]])%2;
27     return root[x]=tmp;
28 }
29 
30 int main(){
31     int T,cas=0;
32     scanf("%d",&T);
33     while(T--){
34         int n,m;
35         scanf("%d%d",&n,&m);
36         memset(val,0,sizeof(val));
37         for(int i=1;i<=n;i++){
38             root[i]=i;
39         }
40         bool flag=true;
41         printf("Scenario #%d:
",++cas);
42         for(int i=1;i<=m;i++){
43             int a,b;
44             scanf("%d%d",&a,&b);
45             int t1=find(a);
46             int t2=find(b);
47             if(t1==t2){
48                 if(val[a]==val[b])
49                     flag=false;
50             }
51             root[t2]=t1;
52             val[t2]=(val[a]-val[b]+1+2)%2;
53         }
54         if(flag)    
55             puts("No suspicious bugs found!
");
56         else
57             puts("Suspicious bugs found!
");
58     }
59     return 0;
60 }