1
#include<iostream>
2
using 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
int parent[MAXN+1];
9
int rank[MAXN+1];
10
int dif[MAXN+1];
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
void Init(int n=MAXN)
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
14
int i;
15
for(i=0;i<=n;i++)
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
17
rank[i]=0;
18
parent[i]=i;
19
dif[i]=-1;
20
}
21
}
22![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
23
int find(int x)
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
25
26
if(parent[x]!=x)
27
parent[x]=find(parent[x]);
28
return parent[x];
29
}
30![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
31
int merge_set(int a,int b)
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
33
if(a==-1) return b;
34
if(b==-1) return a;
35
if(rank[a]>rank[b])
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
37
parent[b]=a;
38
return a;
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
40
parent[a]=b;
41
if(rank[a]==rank[b])
42
rank[b]++;
43
return b;
44
}
45
}
46
void Union(int a,int b)
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
56
int main()
57![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
58
int T,N,M,a,b,i;
59
char c;
60
scanf("%d",&T);
61
while(T--)
62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
63
//memset(parent,0,sizeof(parent));
64
scanf("%d%d",&N,&M);
65
Init(N);
66
while(M--)
67![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
68
scanf(" %c%d%d",&c,&a,&b);
69
if(c=='A')
70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
71
a=find(a);
72
b=find(b);
73
if(a==b)
74
printf("%s\n",string3);
75![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
76
if(a==dif[b])
77
printf("%s\n",string2);
78
else printf("%s\n",string1);
79
}
80
}
81
else
82![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
83
Union(a,b);
84
}
85
}
86
87
}
88
return 0;
89
}
90![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2009-04-21 16:36
wyiu 阅读(137)
评论(0) 编辑 收藏 引用 所属分类:
POJ