poj 1703 Find them, Catch them

 1 //pojFind them, Catch them  1703
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<string>
 6 #include<algorithm>
 7 #include<iostream>
 8 #include<stack>
 9 #include<set>
10 #include<queue>
11 using namespace std;
12 int f[100005];
13 bool c[100005];
14 void Init(int n){
15     int i;
16     for(i=0;i<=n;i++){
17         f[i]=i;
18         c[i]=true;//true表示与父节点在同一组织内
19     }
20 }
21 int find_set(int a){
22     int fa=f[a];
23     if(f[a]!=a){
24         f[a]=find_set(f[a]);
25     }
26     c[a]=(c[fa]==c[a])?true:false;//逻辑判断1
27     return f[a];
28 }
29 void Union(int a,int b,int fa,int fb){
30     f[fa]=fb;
31     c[fa]=(c[a]==c[b])?false:true;//逻辑判断2
32 }
33 int main(){
34     //freopen("D:\\INPUT.txt","r", stdin);
35     int T,n,m,i,a,b;
36     char ch;
37     cin>>T;
38     while(T--){
39         scanf("%d %d\n",&n,&m);//cin>>n>>m;
40         Init(n);
41         for(i=0;i<m;i++){
42             // cin 会导致TLE
43             scanf("%c %d %d\n",&ch,&a,&b);
44             //cin>>ch;
45             //cout<<ch<<endl;
46             //cin>>a>>b;//scanf("%c %d %d\n",&ch,&a,&b);//cin>>ch>>a>>b;
47             int fa,fb;
48             fa=find_set(a);
49             fb=find_set(b);
50             if(ch==‘A‘){
51                 if(fa==fb){
52                     if(c[a]==c[b]){
53                         cout<<"In the same gang."<<endl;
54                     }
55                     else{
56                         cout<<"In different gangs."<<endl;
57                     }
58                 }
59                 else{
60                     cout<<"Not sure yet."<<endl;
61                 }
62             }
63             else{
64                 Union(a,b,fa,fb);//if(fa!=fb)
65             }
66         }
67     }
68     return 0;
69 }