問題描述

有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環(huán)形：A吃B孔轴， B吃C，C吃A贷洲。

現(xiàn)有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莫矗，就是假話砂缩。

你的任務是根據(jù)給定的N（1 <= N <= 50,000）和K句話（0 <= K <= 100,000），輸出假話的總數(shù)庵芭。

解決思路

• 并查集是維護“屬于同一組”的數(shù)據(jù)結構，通過并查集可以將兩個組合并眨唬，以及判斷兩個元素是否屬于同一組好乐。
• 在本題中，并不只有屬于同一類的信息蔚万，還有捕食關系的存在。
• 對于每只動物創(chuàng)建三個元素区转，i-A苔巨、i-B、i-C礁芦，并用這3×N個元素建立并查集：
  1）i-X表示“i屬于種類X”
  2）并查集內的每一個元素表示組內所有元素代表的情況同時發(fā)生或不發(fā)生悼尾。例如，如果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
• 在合并之前要判斷合并是否會產(chǎn)生矛盾：
  對于第一種說法，要判斷i-A和j-B卖鲤、j-C是否已經(jīng)在同一組
  對于第二種說法，要判斷i-A和j-A蛋逾、j-C是否已經(jīng)在同一組

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);
}