1182 - 食物鏈

domen111

http://poj.org/problem?id=1182

AC: http://poj.org/status?problem_id ... 1&result=&language=

並查集(disjoint set)，書裡面的題目，我發現TOJ 89和這題好像

並查集的陣列(ds)需開N*3的大小
每種動物建立3個元素: i-A, i-B, i-C，代表i是A或B或C的情況
unite(i-A, j-B)代表當i為A時，j為B

注意:
1. 這題是單筆測資，如果用多測資輸入會WA
2. 必須使用cstdio，用iostream會TLE

AC code:

#include<cstdio>

#define lie() {ans++;continue;}

using namespace std;

int ds[160000];

int find(int a)

{

    if(ds[a]==a)return a;

    return ds[a]=find(ds[a]);

}

inline void unite(int a,int b)

{

    ds[find(a)]=find(b);

}

inline bool same(int a,int b)

{

    return find(a)==find(b);

}

int main()

{

    int n,k;

    scanf("%d %d",&n,&k);

    for(int i=0;i<n*3;i++)

        ds[i]=i;

    int ans=0;

    for(int i=0;i<k;i++)

    {

        int type,a,b;

        scanf("%d %d %d",&type,&a,&b);

        a--; b--;

        if(a<0 || a>=n || b<0 || b>=n)

            lie();

        if(type==1)

        {

            if(same(a,b+n) || same(a,b+n*2))

                lie();

            unite(a,b);

            unite(a+n,b+n);

            unite(a+n*2,b+n*2);

        }

        else

        {

            if(same(a,b) || same(a,b+n*2))

                lie();

            unite(a,b+n);

            unite(a+n,b+n*2);

            unite(a+n*2,b);

        }

    }

    printf("%d",ans);

}