POJ 1703 Find them, Catch them（并查集变形）

Description

有两个帮派，

给出 D a b 表示a和b位于不同帮派，

给出 A a b 表示询问a和b是否属于同一帮派

并查集

初始化一个 2 * N 的并查集，

如果a和b属于不同帮派，

unite(a, b + n) && unite(b, a + n)

这样如果c和b属于不同帮派

unite(c, b + n) && unite(b, c + n)

就把a和c连起来了

!!!什么神仙做法！！！

是不是暗示我们，有些题多用点空间就能解决问题

Code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;

int n, m;
int pre[N * 2];

void init()
{
    for(int i = 0; i <= n * 2; ++i)
        pre[i] = i;
}

int found(int x)
{
    if(pre[x] != x)
        pre[x] = found(pre[x]);
    return pre[x];
}

void unite(int a, int b)
{
    int x = found(a);
    int y = found(b);
    if(x != y)
        pre[x] = y;
    return ;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        char ch;
        int a, b;
        scanf("%d%d", &n, &m);
        getchar();
        init();
        while(m--)
        {
            ch = getchar();
            scanf("%d%d", &a, &b);
            getchar();
            if(ch == 'D')
            {
                unite(a, b + n);
                unite(b, a + n);
            }
            else
            {
                int x = found(a);
//                int xx = found(a + n);
                int y = found(b);
                int yy = found(b + n);
                if(x == y)
                    cout << "In the same gang.\n";
                else if(x == yy)
                    cout << "In different gangs.\n";
                else
                    cout << "Not sure yet.\n";
            }
        }
    }
    return 0;
}