首页 > 代码库 > POJ 1703 Find them, Catch them

POJ 1703 Find them, Catch them

这道题与POJ 2492 几乎一模一样,就不多说了,直接上代码吧

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 100000 + 10; 8 int p[maxn], r[maxn]; 9 10 int Find(int a)11 {12     if(p[a] == a)    return a;13     int temp = p[a];14     p[a] = Find(p[a]);15     r[a] = (r[a] ^ r[temp]);16     return p[a];17 }18 19 int main(void)20 {21     #ifdef LOCAL22         freopen("1703in.txt", "r", stdin);23     #endif24 25     int T;26     scanf("%d", &T);27     while(T--)28     {29         int n, m, x, y;30         char cmd[10];31         scanf("%d %d", &n, &m);32         for(int i = 0; i <= n; ++i)    p[i] = i;33         memset(r, 0, sizeof(r));34         for(int i = 0; i < m; ++i)35         {36             scanf("%s %d %d", cmd, &x, &y);37             int px = Find(x);38             int py = Find(y);39             if(cmd[0] == A)40             {41                 if(px != py)42                     printf("Not sure yet.\n");43                 else44                 {45                     if((r[x] + r[y]) % 2)46                         printf("In different gangs.\n");47                     else48                         printf("In the same gang.\n");49                 }50             }51             else52             {53                 p[px] = py;54                 r[px] = 1 - (r[x] ^ r[y]);55             }56         }57     }58     return 0;59 }
代码君

 

POJ 1703 Find them, Catch them