種類並查集（POJ1703）

圖學的有點自閉，再加上用到了並查集、模擬棧、搜尋，先補一下這些相對基礎的東西
跟普通並查集區別：
1、陣列開兩倍
2、union_set(a+n,b)和union_set(a,b+n);
3、判斷：
find(a)==find(b)同隊
find(a)==find(b+n)不同隊
不需要再"||f(a+n)==f(b+n)"了

警方決定搗毁兩大犯罪團夥：龍幫和蛇幫，顯然一個幫派至少有一人。該城有N個罪犯，編號從1至N（N<=100000。將有M（M<=100000）次操作。
D a b 表示a、b是不同幫派 A a b 詢問a、b關係 Input 多組數據。第一行是數據總數 T (1 <= T <=
20)每組數據第一行是N、M，接下來M行是操作 Output 對於每一個A操作，回答"In the same gang.「或"In
different gangs.」 或"Not sure yet."

最開始思路是兩個陣列，跟這個有點相似，不過沒分析明白，轉而更加偏向用結構體，不過寫不出來。
思路參考別人的題解，學習到了種類並查集。感覺像是找了個跳板。自己重新寫了一遍。程式碼簡潔明瞭。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>

using namespace std;
const int MAXN = 100005;
int S[2 * MAXN];
int find(int x) {
    int r = x;
    while (S[r] != -1)
        r = S[r];
    int i = x, j;
    while (i != r) {
        j = S[i];
        S[i] = r;
        i = j;
    }
    return r;
}
void union_set(int a, int b) {
    int u = find(a), v = find(b);
    if (u != v) S[v] = u;
}
int main() {
#ifdef LOCAL
    freopen("zz_in.txt", "r", stdin);
    freopen("zz_op.txt", "w", stdout);
#endif
    int t, i, j, k, n, m, a, b;
    char flag;
    cin >> t;
    while (t--) {
        memset(S, -1, sizeof(S));
        scanf("%d %d", &n, &m);
        for (i = 0; i < m; i++) {
            getchar();
            scanf("%c %d %d", &flag, &a, &b);
            if (flag == 'D') {
                union_set(a + n, b);
                union_set(a, b + n);
            }
            if (flag == 'A') {
                if (find(a) == find(b))
                    printf("In the same gang.\n");
                else if (find(a) == find(b + n))
                    printf("In different gangs.\n");
                else
                    printf("Not sure yet.\n");
            }
        }
    }

#ifdef LOCAL
    printf("Time used = %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}