POJ1182——食物链

问题描述

有三类动物A,B,C，这三类动物的食物链构成了有趣的环形：A吃B， B吃C，C吃A。

现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是"1 X Y"，表示X和Y是同类。 第二种说法是"2 X Y"，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1） 当前的话与前面的某些真的话冲突，就是假话；

2） 当前的话中X或Y比N大，就是假话；

3） 当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

---

解决思路

• 并查集是维护“属于同一组”的数据结构，通过并查集可以将两个组合并，以及判断两个元素是否属于同一组。
• 在本题中，并不只有属于同一类的信息，还有捕食关系的存在。
• 对于每只动物创建三个元素，i-A、i-B、i-C，并用这3×N个元素建立并查集：
  1）i-X表示“i属于种类X”
  2）并查集内的每一个元素表示组内所有元素代表的情况同时发生或不发生。例如，如果i-A、j-B属于同一个组，则说明i属于种类A那么j一定属于种类B，反之亦然。
• 对于第一种说法，合并i-A和j-A、i-B和j-B、i-C和j-C
  对于第二种说法，合并i-A和j-B、i-B和j-C、i-C和j-A
• 在合并之前要判断合并是否会产生矛盾：
  对于第一种说法，要判断i-A和j-B、j-C是否已经在同一组
  对于第二种说法，要判断i-A和j-A、j-C是否已经在同一组

---

AC代码

#include "stdio.h"
#include "stdlib.h"

int N;
int K;
int p[150010];
int r[150010];
int res;

//initial the sets
void init(){
    for(int i = 0; i < 3 * N; i++){
        p[i] = i;
    }
}
//Find(x) return the root of x
int Find(int x){
    if(x == p[x]) return x;
    else return p[x] = Find(p[x]);
}

//Union(x, y) union the sets of x and y
void Union(int x, int y){
    int xRoot = Find(x);
    int yRoot = Find(y);

    if(xRoot == yRoot) return;
    if(r[xRoot] < r[yRoot]) p[xRoot] = yRoot;
    else if(r[xRoot] > r[yRoot]) p[yRoot] = xRoot;
    else{
        p[yRoot] = xRoot;
        r[xRoot]++;
    }
}

bool sameRoot(int x, int y){
    //printf("root of %d: %d\n", x, Find(x));
    //printf("root of %d: %d\n", y, Find(y));
    return Find(x) == Find(y);
}

int main(){
    scanf("%d %d", &N, &K);
    init();
    int D, X, Y;
    for(int i = 0; i < K; i++){
        scanf("%d %d %d", &D, &X, &Y);
        //printf("%d %d %d\n", D, X, Y);
        if(X > N || Y > N || (D == 2 && X == Y)) {
            //printf("Input illegal\n");
            res++;
            continue;
        }
        int xA = 3 * X - 3;//x is A
        int xB = 3 * X - 2;//x is B
        int xC = 3 * X - 1;//x is C 
        int yA = 3 * Y - 3;//y is A
        int yB = 3 * Y - 2;//y is B
        int yC = 3 * Y - 1;//y is C
        if(D == 1){
            if(sameRoot(xA, yB) || sameRoot(xA, yC)){
                //printf("conflict:%d and %d are the same\n", X, Y);
                res++;
                continue;
            }
            if(sameRoot(xA, yA)) continue;
            //printf("Union:%d and %d are the same\n", X, Y);
            Union(xA, yA);
            Union(xB, yB);
            Union(xC, yC);
        }   
        if(D == 2){
            if(sameRoot(xA, yA) || sameRoot(xA, yC)){
                //printf("conflict:%d eat %d\n", X, Y);
                res++;
                continue;
            }
            if(sameRoot(xA, yB)) continue;
            //printf("Union:%d eat %d\n", X, Y);
            Union(xA, yB);
            Union(xB, yC);
            Union(xC, yA);
        }
    }
    printf("%d\n", res);
}