题目描述

（大战黑帮）警方决定捣毁两大犯罪团伙：龙帮和蛇帮，显然一个帮派至少有一人。

该城有 $n$ 个罪犯，且这些罪犯一定在这两个帮派的其中一个。编号从 $1$ 至 $N(N\le 100000)$，将有 $M(M\le 100000)$ 次操作。操作有两种。

1. 表示两个罪犯不在一个帮派
2. 询问两个罪犯是否在一个帮派

输入格式

多组数据。

第一行是数据总数 $T (1 \le T \le 20)$ 每组数据第一行是 $N,M$，接下来 $M$ 行是操作。

1. D a b 表示罪犯 $a,b$ 是不同帮派
2. A a b 询问罪犯 $a,b$ 的关系

输出格式

对于每一个 A 操作：

1. 若两个罪犯一定在一个帮派，回答 In the same gang.
2. 若两个罪犯一定不在一个帮派，回答 In different gangs.
3. 如果不确定，回答 Not sure yet.

试补全程序。

思路提示：本题使用了并查集，并且要求每一个 A 操作和 D 操作的平均时间复杂度都为 $O(\operatorname{log}n)$

提醒：一定要弄清楚代码中出现的三个数组的含义，不然你将无法完成本题。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 100100;
int fa[maxn], h[maxn], num[maxn];
int t, n, m;
int get(int x) {
    if (fa[x] == x) {
        return x;
    }
    return ①;
}
void merge(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
        fa[y] = x;
        ②;
    }
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            h[i] = 0;
            fa[i] = i;
            num[i] = ③;
        }
        for (int i = 1; i <= m; i++) {
            char ch;
            int x, y;
            getchar();
            scanf("%c%d%d", &ch, &x, &y);
            if (ch == 'D') {
                if (h[y] == 0) {
                    h[y] = x;
                } else {
                    merge(h[y], x);
                }
                if (④) {
                    h[x] = y;
                } else {
                    merge(h[x], y);
                }
            } else {
                int tmp1 = get(x);
                int tmp2 = get(y);
                if (tmp1 == tmp2) {
                    cout << "In the same gang.\n";
                } else if (⑤) {
                    cout << "In different gangs.\n";
                } else {
                    cout << "Not sure yet.\n";
                }
            }
        }
    }
    return 0;
}

1. ① 处应填 {{ select(1) }}

• fa[x] = get(fa[x])
• get(fa[x])
• x = get(fa[x])
• fa[x]

2. ② 处应填 {{ select(2) }}

• num[y] += num[x]
• 不填
• num[x] = num[y]
• num[x] += num[y]

3. ③ 处应填 {{ select(3) }}

• i
• 0
• 1
• n

4. ④ 处应填 {{ select(4) }}

• h[x] == 0
• h[x] != 0
• h[x] != y
• h[x] == y

5. ⑤ 处应填 {{ select(5) }}

• tmp1 == get(h[y])
• tmp1 == get(h[y]) || num[tmp1] == n - 1 && num[tmp2] == 1 || num[tmp1] == 1 && num[tmp2] == n - 1
• tmp2 == get(h[x])
• tmp1 == get(h[y]) || num[tmp1] == n - 1 + num[tmp2] == n