POJ 1182 并查集

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

有 $N$ 只动物,编号 $1…N$,所有动物都属于 $A, B, C$ 其中一种。已知 $A$ 吃 $B$,$B$ 吃 $C$,$C$ 吃 $A$。按顺序给出以下两类信息:

  1. $x,y$ 属于同一类
  2. $x$ 吃 $y$

这些信息可能有错或者与之前的冲突。一切以先出现的信息为准,统计出错的信息数量。

思路

为每只动物创建三个元素:$i_A, i_B, i_C$,分别表示其属于种类 $A, B, C$。

例如如果 $i_A, j_B$ 出现在同一组里,意味着如果 $i$ 属于 $A$,则 $j$ 一定属于 $B$。因此对于两类信息的处理如下:

  1. $x,y$ 属于同一类:合并 $x_A, y_A$、$x_B, y_B$ 和 $x_C, y_C$
  2. $x$ 吃 $y$:合并 $x_A, y_B$、$x_B, y_C$ 和 $x_C, y_A$

当然在合并之前需要判断合法性。

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

int par[maxn], rk[maxn], n, k;

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() {
for (int i = 0; i < maxn; i++)
par[i] = i;
scanf("%d %d", &n, &k);
int wrong = 0;
for (int i = 0; i < k; i++) {
int opt, x, y;
scanf("%d %d %d", &opt, &x, &y);
x--; y--;
if (x >= n || y >= n) {
wrong++;
continue;
}
if (opt == 1) { // same
if (getfa(x) == getfa(y + n) || getfa(x + n) == getfa(y)) {
wrong++;
continue;
}
link(x, y);
link(x + n, y + n);
link(x + 2 * n, y + 2 * n);
} else { // x eat y
if (getfa(x) == getfa(y) || getfa(x + n) == getfa(y)) {
wrong++;
continue;
}
link(x, y + n);
link(x + n, y + 2 * n);
link(x + 2 * n, y);
}
}
printf("%d\n", wrong);
return 0;
}