并查集。

这题错了不少次才过的。

分析见代码。

 

 

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 const int maxn = 1e5 + 10; 6 const char str1[] = "Not sure yet."; 7 const char str2[] = "In different gangs."; 8 const char str3[] = "In the same gang."; 9 int fa[maxn], belong[maxn], nex[maxn];10 int n, m, u, v, k;11 char op;12 13 int father(int u){14     //WHAT WOULD CAUSE AN INFINITE LOOP15     if(fa[u] == -1) return u;16     int tem = father(fa[u]);17     belong[u] = belong[tem];18     fa[u] = tem;19     return tem;20 }21 22 void solve(){23     if(op == 'D'){24         if(belong[u] == -1 && belong[v] == -1){25             //this is the simplest case26             belong[u] = k++;27             belong[v] = k++;28             nex[u] = v;29             nex[v] = u;30             return;31         }32         if(belong[u] != -1 && belong[v] == -1){33             //notice that v is never mentioned, but u is already processed34             //since is u is vistied, u got its partner35             int fu = father(u), fu1 = father(nex[u]);36             //draw a line from v to u137             fa[v] = fu1;38             nex[v] = fu;39             belong[v] = belong[fu1];40             return;41             //match a virtue partner for node u42         }43         if(belong[u] == -1 && belong[v] != -1){44             int fv = father(v), fv1 = father(nex[v]);45             fa[u] = fv1;46             nex[u] = fv;47             belong[u] = belong[fv1];48             return;49         }50         if(belong[u] != -1 && belong[v] != -1){51             //notice that both u and v is already visited52             int fu = father(u), fu1 = father(nex[u]);53             int fv = father(v), fv1 = father(nex[v]);54             int bu = belong[fu] >> 1;55             int bv = belong[fv] >> 1;56             if(bu > bv){57                 // v is relatively primitive58                 fa[fu] = fv1;59                 fa[fu1] = fv;60                 return;61             }62             if(bu < bv){63                 fa[fv] = fu1;64                 fa[fv1] = fu;65                 return;66             }67         }68     }69     if(op == 'A'){70         int fu = father(u);71         int fv = father(v);72         if(belong[fu] == -1 || belong[fv] == -1) puts(str1);73         else if(belong[fu] == belong[fv]) puts(str3);74         else if(belong[fu] == (1 ^ belong[fv])) puts(str2);75         else puts(str1);76     }77 }78 79 int main(){80     freopen("in.txt", "r", stdin);81     int T;82     scanf("%d", &T);83     while(T--){84         scanf("%d%d", &n, &m);85         memset(belong, -1, sizeof belong);86         memset(fa, -1, sizeof fa);87         k = 0;88         for(int i = 0; i < m; i++){89             scanf(" %c%d%d", &op, &u, &v);90             solve();91         }92     }93 }