POJ 1703 并查集

题目链接:http://poj.org/problem?id=1703

有 $N$ 个罪犯,每个罪犯要么属于青龙帮,要么属于毒蛇帮。

按顺序给出 $N$ 个操作,分别为情报和询问:

  1. 情报:罪犯 $i$ 和罪犯 $j$ 不是一个帮派的
  2. 询问:罪犯 $i$ 和罪犯 $j$ 是一个帮派的吗?

对于每个询问,要根据现有的情报给出三种回答:

1. Not sure yet.
2. In different gangs.
3. In the same gang.

思路

可以使用并查集解决问题。令两个帮派分别为 $A$, $B$。

为每人创建 2 个元素:$i_A, i_B$,分别表示其属于 $A, B$。例如如果 $i_A, j_B$ 出现在同一组里,意味着如果 $i$ 属于 $A$,则 $j$ 一定属于 $B$。

那么有 $2N$ 个元素,分别为 $1_A, 2_A…N_A; 1_B, 2_B… N_B$,给他们分别标号 $0…2n-1$。

对于情报 $i, j$ 不属于一个帮派,就意味着如果 $i$ 属于 $A$,那么 $j$ 一定属于 $B$;如果 $i$ 属于 $B$,那么 $j$ 一定属于 $A$。因此只需要将 $i_A$ 和 $j_B$ 联结,将 $i_B$ 和 $j_A$ 联结即可。

1703.cppview raw
#include <iostream>
#include <stdio.h>
#define maxn 200005
using namespace std;

int par[maxn], rk[maxn];
int T, n, m;

int getfa(int x) {
return x == par[x] ? x : getfa(par[x]);
}

void link(int x, int y) {
x = getfa(x); y = getfa(y);
if (x == y) return;
if (rk[x] < rk[y]) {
par[x] = y;
} else {
par[y] = x;
if (rk[x] == rk[y]) rk[x]++;
}
}

int main() {
cin >> T;
while (T--) {
for (int i = 0; i < maxn; i++)
par[i] = i;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
char opt; int x, y;
scanf(" %c %d %d", &opt, &x, &y);
if (opt == 'A') {
if (getfa(x) == getfa(y))
puts("In the same gang.");
else if (getfa(x) == getfa(y + n))
puts("In different gangs.");
else
puts("Not sure yet.");
} else {
link(x, y + n);
link(x + n, y);
}
}
}
return 0;
}