题意:
两个两个输入一些数,D代表这两个数不同,A代表查询这两个数是否相同
要点:
与食物链那一题类似,都是开多倍数组,储存每种情况
| 15321734 | Seasonal | 1703 | Accepted | 1680K | 375MS | C++ | 973B | 2016-03-27 18:34:06 |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 100050
int p[maxn * 2], rank[maxn * 2];
int m, n;void init()
{for (int i = 1; i <= 2*m; ++i)//注意这里初始化要2*m{p[i] = i;rank[i] = 0;}
}
int find(int x)
{if (p[x] == x) return x;return p[x] = find(p[x]);
}
void merge(int x, int y)
{x = find(x);y = find(y);if (x == y) return;if (rank[x] > rank[y])p[y] = x;else{p[x] = y;if (rank[x] == rank[y]) ++rank[y];}
}
bool same(int x, int y)
{return find(x) == find(y);
}
int main()
{int t,i,x,y;char str;scanf("%d", &t);while (t--){scanf("%d%d", &m, &n);getchar();init();while(n--){scanf("%c%d%d", &str,&x,&y);getchar(); //这一步比较重要,清除缓冲区if (str == 'A'){if (same(x, y))printf("In the same gang.\n");else if (same(x, y + m))printf("In different gangs.\n");elseprintf("Not sure yet.\n");}else{merge(x, y + m);//合并X为A,Y为B的情况merge(x + m, y);//合并X为B,Y为A的情况}}}return 0;
}