1 #include <cstdio> 2 #include <iostream> 3 #define N 200001 4  5 int T, n, m; 6 int f[N]; 7  8 inline int read() 9 {10     int x = 0, f = 1;11     char ch = getchar();12     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;13     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;14     return x * f;15 }16 17 inline int find(int x)18 {19     return x == f[x] ? x : f[x] = find(f[x]);20 }21 22 inline void connect(int x, int y)23 {24     x = find(x);25     y = find(y);26     f[x] = y;27 }28 29 int main()30 {31     int i, j, x, y;32     char s[1];33     T = read();34     while(T--)35     {36         n = read();37         m = read();38         for(i = 1; i <= (n << 1); i++) f[i] = i;39         for(i = 1; i <= m; i++)40         {41             scanf("%s", s);42             x = read();43             y = read();44             if(s[0] == ‘A‘)45             {46                 if(find(x) == find(y)) puts("In the same gang.");47                 else if(find(x) == find(y + n) || find(y) == find(x + n)) puts("In different gangs.");48                 else puts("Not sure yet.");49             }50             else51             {52                 connect(x, y + n);53                 connect(y, x + n);54             }55         }56     }57 } 

 1 #include <cstdio> 2 #include <iostream> 3 #define N 1000001 4  5 int T, n, m; 6 int f[N], d[N]; 7  8 inline int read() 9 {10     int x = 0, f = 1;11     char ch = getchar();12     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;13     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;14     return x * f;15 }16 17 inline int find(int x)18 {19     if(x ^ f[x])20     {21         int fx = f[x];22         f[x] = find(f[x]);23         d[x] = (d[x] + d[fx]) % 2;24     }25     return f[x];26 }27 28 inline void connect(int x, int y)29 {30     int fx = find(x), fy = find(y);31     d[fx] = (d[y] + 1 - d[x]) % 2;32     f[fx] = f[y];33 }34 35 int main()36 {37     int i, x, y;38     char s[1];39     T = read();40     while(T--)41     {42         n = read();43         m = read();44         for(i = 1; i <= n; i++) f[i] = i, d[i] = 0;45         for(i = 1; i <= m; i++)46         {47             scanf("%s", s);48             x = read();49             y = read();50             if(s[0] == ‘D‘) connect(x, y);51             else52             {53                 if(find(x) ^ find(y)) puts("Not sure yet.");54                 else if(d[x] == d[y]) puts("In the same gang.");55                 else puts("In different gangs.");56             }57         }58     }59     return 0;60 }