poj 1703 并查集

题意：在这个城市里有两个黑帮团伙，现在给出N个人，问任意两个人他们是否在同一个团伙
输入D x y代表x于y不在一个团伙里
输入A x y要输出x与y是否在同一团伙或者不确定他们在同一个团伙里

链接：点我

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <string.h>
 5 using namespace std;
 6 
 7 const int MAXN=100010;
 8 int F[MAXN];
 9 int val[MAXN];
10 int find(int x)
11 {
12     if(F[x]==-1)return x;
13     int tmp=find(F[x]);
14     val[x]=(val[x]+val[F[x]])%2;
15     return F[x]=tmp;
16 }
17 void bing(int x,int y)
18 {
19     int t1=find(x);
20     int t2=find(y);
21     if(t1!=t2)
22     {
23         F[t1]=t2;
24         val[t1]=(val[y]-val[x]+1)%2;
25     }
26 }
27 int main()
28 {
29     int T;
30     char str[10];
31     int u,v;
32     int n,m;
33     scanf("%d",&T);
34     while(T--)
35     {
36         scanf("%d%d",&n,&m);
37         memset(F,-1,sizeof(F));
38         memset(val,0,sizeof(val));
39         while(m--)
40         {
41             scanf("%s%d%d",&str,&u,&v);
42             if(str[0]=='A')
43             {
44                 if(find(u)!=find(v))
45                 {//题目说两个集团至少有一个人，所以N==2的时候单独考虑，但是不考虑这个也可以AC，估计没有这样的数据
46                     if(n==2)printf("In different ganges.
");
47                     else printf("Not sure yet.
");
48                 }
49                 else
50                 {
51                     if(val[u]!=val[v])printf("In different gangs.
");
52                     else printf("In the same gang.
");
53                 }
54             }
55             else
56             {
57                 bing(u,v);
58             }
59         }
60     }
61     return 0;
62 }