POJ - 1182 食物链（并查集）

原题：传送门
思路：
对于动物i，i表示i号动物属于A类，i+N表示i号动物属于B类，i+2*N表示i号动物属于C类
对于每一条信息，做如下处理：

1： 通过并查集检查x和y+N的关系，x和y+2N的关系（x和y必须不存在吃与被吃，否则这条就是错误信息），合并x和y、x+N和Y+N、x+2N和y+2N
2： 通过并查集检查x和y的关系，x和y+2N的关系（x和y必须不属于同类，并且y不能吃x），合并x和y+N、x+N和y+2N、x+2N和y

Code：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 1000007;int pre[maxn];
int rk[maxn];
int N, K;void init() {
    for (int i=1;i<=3*N;i++) {
    pre[i] = i;rk[i] = 0;}
}
int find_pre(int x) {
    return x == pre[x] ? x : pre[x] = find_pre(pre[x]);
}
void merge(int x, int y) {
    x = find_pre(x), y = find_pre(y);if (x != y) {
    if (rk[x] < rk[y]) {
    pre[x] = y;} else {
    pre[y] = x;if (rk[x] == rk[y])  rk[x]++;}}
}
bool same(int x, int y) {
    return find_pre(x) == find_pre(y);
}
int main()
{
    int ans = 0;scanf("%d %d", &N, &K);int d, x, y;init();while (K--) {
    scanf("%d %d %d", &d, &x, &y);if (x<1 || x>N || y<1 || y>N) {
    ans++;continue;}if (d == 1) {
    if (same(x, y+N) || same(x, y+2*N)) {
    ans++;} else {
    merge(x, y);merge(x+N, y+N);merge(x+2*N, y+2*N);}} else {
    if (same(x, y) || same(x, y+2*N)) {
    ans++;} else {
    merge(x, y+N);merge(x+N, y+2*N);merge(x+2*N, y);}}}printf("%d\n", ans);return 0;
}