【POJ-1703】Find them, Catch them | 并查集

并查集中的巧妙合并

题意：
一个城市有两个集团，D [a] [b]表示a,b不在一个集团，A [a] [b]表示查询a,b在不在一个集团，根据已知做出三种回答。
分析：
由于仅有两个帮派，所以可以这样想:每个节点i再衍生出一个新的节点i + n， 当a，b属于不同帮派的时候，可以将a和b + n合并到一个帮派， b和a + n合并到一个帮派，实属巧妙。
代码：

#include <iostream>
#include <string>
using namespace std;
const int maxn = 1e5 + 10;
int fa[maxn << 1];

int n, m;

int find(int x)
{
    return fa[x] = x == fa[x] ? x : find(fa[x]);
}
void init()
{
    for(int i = 1; i <= n << 1; i++)
        fa[i] = i;
}

int main()
{

    int t; cin >> t;
    while(t--)
    {
        cin >> n >> m;
        init();
        while(m--)
        {
            char ope[2];
            int a, b;
            scanf("%s%d%d", ope, &a, &b);
            if(ope[0] == 'A')
            {
                if(find(a) == find(b)) cout << "In the same gang." << endl;
                else if(find(a) == find(b + n)) cout << "In different gangs." << endl;
                else cout << "Not sure yet." << endl;
            }
            else
            {
                fa[find(a)] = find(b + n);;
                fa[find(b)] = find(a + n);
            }
        }
    }
}