poj1703 并查集，维护不同集合

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int maxn=1e5+100;
 6 int head=0,tail=10002;
 7 int n,m;
 8 int father[maxn*2],rank[maxn*2],vis[maxn*2];
 9 int findf(int x)
10 {
11     int k, j, r;
12     r = x;
13     while(r != father[r])
14         r = father[r];
15     k = x;
16     while(k != r)
17     {
18         j = father[k];
19         father[k] = r;
20         k = j;
21     }
22     return r;
23 }
24 
25 void merg(int x,int y)
26 {
27     int fx=findf(x);
28     int fy=findf(y);
29     if(rank[fx]<=rank[fy])
30     {
31         father[fy]=fx;
32         rank[fx]++;
33     }
34     else
35     {
36         father[fx]=fy;
37         rank[fy]++;
38     }
39 }
40 void ini()
41 {
42     for(int i=0;i<=2*maxn;i++) father[i]=i;
43     father[tail]=tail;
44     memset(rank,0,sizeof(rank));
45 }
46 void solve()
47 {
48     scanf("%d%d",&n,&m);
49     ini();
50     for(int i=1;i<=m;i++)
51     {
52         char a;int b,c;
53         cin>>a;scanf("%d%d",&b,&c);
54         if(a=='A')
55         {
56             //for(int i=1;i<=n;i++) printf("%d ",father[i]);puts("");
57                 if(findf(b)==findf(c)||findf(b+n)==findf(c+n))
58                     puts("In the same gang.");
59                 else if(findf(b)==findf(c+n)||findf(c)==findf(b+n))
60                     puts("In different gangs.");
61                 else puts("Not sure yet.");
62         }
63         else
64         {
65             merg(b,c+n);
66             merg(c,b+n);
67         }
68     }
69 }
70 
71 int main()
72 {
73     //freopen("in.txt","r",stdin);
74     int T;
75     cin>>T;
76     for(int i=1;i<=T;i++) solve();
77 }