思路

并查集

每个联通图内的元素之间都有相对关系$rank$，关系$rank$差$1$说明元素在不同的集团，$rank$相同说明在同一个集团。 询问$a$，$b$结点的关系的时候，当$a$，$b$不在一个联通图是关系未确定。$a$，$b$在一个联通图则比较$rank$

标程

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>

const int MAXN = 1000005;
int pre[MAXN];
int ranks[MAXN];

int find_DS(int r) {
    if (r == pre[r]) return r;
    int fa = pre[r];
    pre[r] = find_DS(pre[r]);
    ranks[r] = (ranks[r] + ranks[fa]) % 2;
    return pre[r];
}

bool merge_DS(int a, int b) {
    int fx = find_DS(a), fy = find_DS(b);
    if (fx == fy) return 0;
    pre[fx] = fy;
    ranks[fx] = (-ranks[a] + ranks[b] + 1) % 2;
    return 1;
}

int main() {
    int T, N, M, a, b, i;
    char s[2];
    std::cin >> T;
    while (T--) {
        std::cin >> N >> M;
        for (i = 1; i <= N; i++) {
            pre[i] = i;
            ranks[i] = 0;
        }
        for (i = 0; i < M; i++) {
            std::scanf("%s%d%d", s, &a, &b);
            if (s[0] == 'D') {
                merge_DS(a, b);
            } else {
                int fa = find_DS(a), fb = find_DS(b);
                if (fa != fb) std::printf("Not sure yet.\n");
                else if (ranks[a] == ranks[b]) std::printf("In the same gang.\n");
                else std::printf("In different gangs.\n");
            }
        }
    }
    return 0;
}