1
#include<iostream>
2using namespace std;
3#define MAXN 100000
4#define string1 "Not sure yet."
5#define string2 "In different gangs."
6#define string3 "In the same gang."
7
8int parent[MAXN+1];
9int rank[MAXN+1];
10int dif[MAXN+1];
11
12void Init(int n=MAXN)
13
{
14
int i;
15 for(i=0;i<=n;i++)
16
{
17 rank[i]=0;
18 parent[i]=i;
19 dif[i]=-1;
20
}
21
}
22
23int find(int x)
24{
25
26 if(parent[x]!=x)
27 parent[x]=find(parent[x]);
28 return parent[x];
29}
30
31int merge_set(int a,int b)
32{
33 if(a==-1) return b;
34 if(b==-1) return a;
35 if(rank[a]>rank[b])
36 {
37 parent[b]=a;
38 return a;
39 }else{
40 parent[a]=b;
41 if(rank[a]==rank[b])
42 rank[b]++;
43 return b;
44 }
45}
46void Union(int a,int b)
47{
48 int root1=find(a),
49 root2=find(b),
50 da=merge_set(dif[root1],root2), //b的新根
51 db=merge_set(root1,dif[root2]); //a的新根
52 dif[db]=da;
53 dif[da]=db;
54}
55
56int main()
57{
58 int T,N,M,a,b,i;
59 char c;
60 scanf("%d",&T);
61 while(T--)
62 {
63 //memset(parent,0,sizeof(parent));
64 scanf("%d%d",&N,&M);
65 Init(N);
66 while(M--)
67 {
68 scanf(" %c%d%d",&c,&a,&b);
69 if(c=='A')
70 {
71 a=find(a);
72 b=find(b);
73 if(a==b)
74 printf("%s\n",string3);
75 else {
76 if(a==dif[b])
77 printf("%s\n",string2);
78 else printf("%s\n",string1);
79 }
80 }
81 else
82 {
83 Union(a,b);
84 }
85 }
86
87 }
88 return 0;
89}
90
posted on 2009-04-21 16:36
wyiu 閱讀(147)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ