1 //并查集
2 #include<iostream>
3 #define MaxN 100000
4 typedef struct{
5 int fparent;
6 int frank;
7 int others;
8 }NODE;
9 NODE S[MaxN+1];
10 void init(int n)
11 {
12 for(int i=1;i<=n;i++){
13 S[i].fparent=i;
14 S[i].frank=0;
15 S[i].others=-1;
16 }
17 }
18 int find_set(int x)
19 {
20 if(x==-1)return -1;
21 if(S[x].fparent!=x)
22 S[x].fparent=find_set(S[x].fparent);
23 return S[x].fparent;
24 }
25 int union_set(int x,int y)
26 {
27 if(x==-1)return y;
28 if(y==-1)return x;
29 if(S[x].frank>S[y].frank)
30 {
31 S[y].fparent=x;
32 return x;
33 }
34 else {
35 S[x].fparent=y;
36 if(S[x].frank==S[y].frank)
37 S[y].frank++;
38 return y;
39 }
40 }
41 void make(int x,int y)//x is the enemy of y
42 {
43 int tx,ty;
44 x=find_set(x);
45 y=find_set(y);
46 tx=union_set(S[x].others,y);//這是x敵人團伙的合并，也是y朋友團伙的合并，對于ｙ來說x的敵人也是y的朋友
47 //tx是x敵人團伙合并后新的頭,y朋友團伙合并后新的頭
48 ty=union_set(x,S[y].others);//這是y敵人團伙的合并，也是x朋友團伙的合并,對于x來說y的敵人也是x的朋友
49 //ty是y敵人團伙合并后新的頭,x朋友團伙合并后新的頭
50 S[tx].others=ty;//注意union_set返回的永遠是頭
51 S[ty].others=tx;
52 }
53 int main()
54 {
55 int T,N,M,i,p,q;
56 char X;
57 scanf("%d",&T);
58 while(T>0){
59 T--;
60 scanf("%d%d",&N,&M);
61 getchar();
62 init(N);
63 for(i=0;i<M;i++){
64 scanf("%c %d %d",&X,&p,&q);
65 getchar();
66 if(X=='A'){
67 p=find_set(p);
68 q=find_set(q);
69 if(p==q)printf("In the same gang.\n");
70 else if(p==S[q].others)printf("In different gangs.\n");
71 else printf("Not sure yet.\n");}
72 else if(X=='D')
73 make(p,q);
74 }
75 }
76 return 0;
77 }
http://acm.pku.edu.cn/JudgeOnline/problem?id=1703
posted on 2008-01-27 15:55
zoyi 閱讀(470)
評論(0) 編輯 收藏 引用