POJ 1703 Find them, Catch them——并查集

POJ 1703 Find them, Catch them——并查集

题意：有两个集合，n个物品，标号为1~n，m个操作，d操作表示两个物品不在同一集合，a操作表示判断两个物品间的关系

思路：设两个物品为x y，不在统一集合可以用并查集合并x+n，y以及x，y+n，判断时如果x和y在同一集合且x+n，y以及x，y+n不在同一集合则说明x和y在同一集合，如果x和y在不同集合且x+n，y以及x，y+n在同一集合则说明x和y在不同集合，否则无法判断

#include #include #include #include using namespace std;const int maxn = 2 * 1e5 + 10;int T, N, M, par[maxn], ran[maxn];void Init() { for (int i = 0; i <= (N<<1); i++) par[i] = i, ran[i] = 0;}int Query(int x) { return par[x] == x ? x : par[x] = Query(par[x]); }void Union(int x, int y) { x = Query(x), y = Query(y); if (x == y) return; if (ran[x] < ran[y]) par[x] = y; else { par[y] = x; if (ran[x] == ran[y]) ran[x]++; }}bool Same(int x, int y) { return Query(x) == Query(y);}int main() { scanf("%d", &T); while (T--) { scanf("%d %d", &N, &M); Init(); while (M--) { char c[2]; int a, b; scanf("%s%d%d", c, &a, &b); if (c[0] == 'D') { Union(a + N, b); Union(a, b + N); } else { bool ok1 = Same(a, b), ok2 = Same(a + N, b), ok3 = Same(a, b + N); if (ok1 && !ok2 && !ok3) printf("In the same gang.\n"); else if (!ok1 && ok2 && ok3) printf("In different gangs.\n"); else printf("Not sure yet.\n"); } } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。