首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。