[poj1182]食物鏈(并查集+補集) - Pumbit-Legion @ IT工程師數位筆記本

文章出處

食物鏈

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 64841		Accepted: 19077

Description

動物王國中有三類動物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），輸出假話的總數。

Input

第一行是兩個整數N和K，以一個空格分隔。
以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。
若D=1，則表示X和Y是同類。
若D=2，則表示X吃Y。

Output

只有一個整數，表示假話的數目。

Sample Input

Sample Output

Source

Noi 01

關于用補集來解決并查集元素間關系的方法，請自行百度

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<algorithm>
#include<queue>
#define LL long long
int fa[150020],size[150020];
int n;
inline int read(){
       int sum=0;char ch=getchar();
       while(ch>'9'||ch<'0')ch=getchar();
       while(ch<='9'&&ch>='0'){
             sum=sum*10+ch-'0';
             ch=getchar();
       }
       return sum;
}
inline int fnd(int x){
    int r=x,tmp;
    while(x!=fa[x])x=fa[x];
    while(r!=x)tmp=fa[r],fa[r]=x,r=fa[r];
    return x;
}
inline int uni(int x,int y){
    int fx=fnd(x);
    int fy=fnd(y);
    if(size[fx]<size[fy])fa[fx]=fy;
    else if(size[fx]>size[fy])fa[fy]=fx;
    else{
        fa[fy]=fx;
        ++size[fx];
    }
    return 0;
}
int main(){
    int k;
    n=read(),k=read();
    int i,d,x,y,cnt=0;
    for(int i=1;i<=n*3;++i)fa[i]=i;
    for(i=1;i<=k;++i){
        d=read(),x=read(),y=read();
        if(x>n||y>n||(x==y&&d==2)){
           ++cnt;
           continue;
        }
        int fx=fnd(x),fy=fnd(y);
        int fx1=fnd(x+n),fy1=fnd(y+n); //?
        int fx2=fnd(x+2*n),fy2=fnd(y+2*n); //??
        if(d==1){
           if(fx==fy1||fx==fy2){
              cnt++;
              continue;
           }else{
               uni(fx,fy);
               uni(fx1,fy1);
               uni(fx2,fy2);
           }
        }else{
            if(fx==fy||fx==fy1){
                cnt++;
                continue;
            }else{
                uni(fx1,fy);
                uni(fx2,fy1);
                uni(fy2,fx);
            }
        }
    }
    printf("%d",cnt);
    return 0;
}