poj 1182食物連鎖(クラシック!種類と調査集)

リンク:
http://poj.org/problem?id=1182
原題:
Description
動物王国には3種類の動物A,B,Cがあり,この3種類の動物の食物連鎖は興味深い環状を構成している.AはBを食べ、BはCを食べ、CはAを食べる. 
既存のN個の動物は、1−Nで番号付けされている.どの動物もA,B,Cの一種ですが、どれなのか分かりません. 
このN個の動物が構成する食物連鎖関係を2つの説で説明する人がいる. 
1つ目の言い方は「1 X Y」で、XとYが同類であることを表す. 
2つ目の言い方は「2 X Y」で、XがYを食べることを意味します. 
この人はN個の動物に対して、上記の2つの言い方を使って、次から次へとK文の言葉を言って、このK文の言葉はあるのは本当で、あるのは偽物です.一言が次の3つの1つを満たすと、この言葉はうそで、そうでなければ本当のことです. 
1)現在の話は前のいくつかの本当の話と衝突し、うそである. 
2)現在の話ではXやYがNより大きく、うそである. 
3)現在の言葉はXがXを食べることを意味し,うそである. 
あなたの任務は、与えられたN(1<=N<=50000)とK文(0<=K<=100000)に基づいて、偽話の総数を出力することです. 
Input
最初の行は2つの整数NとKで、1つのスペースで区切られています. 
以下のK行は、行ごとに3つの正の整数D,X,Yであり、2つの数の間に1つのスペースで区切られており、Dは言い方の種類を表す. 
D=1であれば、XとYは同類であることを示す. 
D=2なら、XがYを食べることを表す.
Output
うその数を表す整数は1つしかありません.
Sample Input

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

Sample Output

3

分析とまとめ:
この問題は少し複雑な種類で、3種類の動物が集まっているので、明らかに3種類に分けるべきだ.
xがyを食べると仮定すると,xはyの重みより1.大きい3種類の動物がいるため,重みは0,1,2の3種類に分けられる.0はルートノードで、あるノードの重み値が1であれば、このノードがルートノードを食べることを示し、重み値が2であれば2が1を食べることを示す(2は1より大きい)が、3種類の動物が循環して食べる関係で、2は0に食べられる.
次に、連結時にリレーショナル・カテゴリに従ってウェイト値を計算します.
コード:

#include<cstdio>

const int N = 50005;
int n, m, f[N], rank[N];

inline void init(){
    for(int i=0; i<=n; ++i)
        f[i]=i,rank[i]=0;
}

int find(int x){
    if(x==f[x])return x;
    int fa=f[x];
    f[x]=find(f[x]);
    rank[x] = (rank[x]+rank[fa])%3;
    return f[x];
}

inline bool Union(int x,int y,int D){
    int a=find(x), b=find(y);
    if(a==b){
        if(D==1&&rank[x]!=rank[y]) return false;
        if(D==2){
            if(rank[x]==2&&rank[y]!=1)return false;
            if(rank[x]==1&&rank[y]!=0)return false;
            if(rank[x]==0&&rank[y]!=2)return false;
        }
        return true;
    }
    f[a] = b;
    if(D==2){
        rank[a] = (rank[y]-rank[x]+3+1)%3; //    3，       
    }
    else{
        rank[a] = (rank[y]-rank[x]+3)%3;   //     3，       
    }
    return true;
}

int main(){
    int x,y,d;
    scanf("%d%d",&n,&m);
    init();
    int cnt=0;
    for(int i=0; i<m; ++i){
        scanf("%d%d%d",&d,&x,&y);
        if(x>n || y>n || d==2&&x==y){
            ++cnt; continue;
        }
        if(!Union(x,y,d)) {
            ++cnt;
        }
    }
    printf("%d
", cnt);
    return 0;
}

——       ，       。
  
   
  
  
  

    
   
   
             
   
  
  
  
   
  
  
  

    
   
   
           http://blog.csdn.net/shuangde800 ， By   D_Double  (     )