種類并查集

北京大學OJ1182

食物鍊

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 64641	Accepted: 18999

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

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

source code:      

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

std::vector<pair<int,int> > w;
std::vector<pair<int,int> > d;
int num,len,fakeNum;

struct node{
    int relation;//和父親的關系，涉及到兩個和兩個以上的種類
    int father;//父親序号
    //int value;//用于需要統計的題
};

std::vector<node> nodes;

void init(){
    for (int i = 0 ; i < num ; i++){
        node nn;
        nn.father = i;
        //nn.value = 1;
        nn.relation = 0;//0代表是同一類，1代表吃掉父親，2代表被父親吃掉
        nodes.push_back(nn);
    }
}

//不同題目這個函數會不同
int getRelation(int a, int b ){//已知a = (x,y) b = (y,z),求c = (x,z)
    int c = 0;
    
    if(a == 0){
        return b;
    }

    if (a == 1){
        if(b == 0){
            return 1;
        }
        if(b == 1){
            return 2;
        }
        if(b == 2){
            return 0;
        }
    }

    if (a == 2){
        if(b == 0){
            return 2;
        }
        if(b == 1){
            return 0;
        }
        if(b == 2){
            return 1;
        }
    }
}

//不同題目這個函數會不同
int reverseRalation(int a){
    if(a == 0){
        return 0;
    }
    if(a == 1){
        return 2;
    }
    if(a == 2){
        return 1;
    }
}

void updateNode(int x, int root){//這裡假設x的父親是根節點或者是根節點的孩子
    if (nodes[x].father == root){
        return;
    }
    
    int f = nodes[x].father;
    //relation和value更新,不同題目規則不同
    nodes[x].relation = getRelation(nodes[x].relation,nodes[f].relation);
    //nodes[f].value -= 1; 
    nodes[x].father = root;
}

int getRoot(int x){
    int fi = nodes[x].father;
    if (fi == x){
        return fi;
    }
    int re = getRoot(fi);
    
    updateNode(x,re);
    return re;
}


void mergeUpdate(int x,int y,int xr,int yr,int relation){
    nodes[yr].father = xr;

    //relation和value更新,不同題目規則不同
    int xTOyr = getRelation(relation,nodes[y].relation);
    int yrTOx = reverseRalation(xTOyr);
    int yrTOxr= getRelation(yrTOx,nodes[x].relation);

    nodes[yr].relation = yrTOxr;
    
    //nodes[xr].value += nodes[yr].value;
}

bool isHarmonious(int x, int y, int relation){
    int rTOy = reverseRalation(nodes[y].relation);
    int xTOy = getRelation(nodes[x].relation,rTOy);
    return relation == xTOy;
}

bool merge(int x , int y, int relation){
    int xr = getRoot(x);
    int yr = getRoot(y);
    if(xr == yr){
        return isHarmonious(x,y,relation);
    }
    else{
        mergeUpdate(x,y,xr,yr,relation);
        
        return true;
    }
}

bool judge(int x , int y){
    int xr = getRoot(x);
    int yr = getRoot(y);
    if (xr == yr){
        return true;
    }
    else{
        return false;
    }
}

int goodState(int type, int x, int y){
    if (x>num || y > num){
        return -1;
    }
    if (x==y && type!=1){
        return -1;
    }
    return type-1;
}
struct data
{    
    int ty;
    int f;
    int s;
    
};
std::vector<data> all;

void input(){
    fakeNum = 0;
    cin >> num >> len;
    
    init();
    for (int i = 0 ; i < len ; i ++){
        int ty;
        int f, s;
        scanf("%d%d%d",&ty,&f,&s);
        
        //cout << ty << " " << f << " " << s <<endl;
        data d;
        d.ty = ty;
        d.f = f;
        d.s = s; 
        all.push_back( d );
        // all.push_back(s);
        // if (ty == 1){
        //     d.push_back(make_pair<int,int>(f,s) );
        // }
        // else{
        //     w.push_back(make_pair<int,int>(f,s) );
        // }
        
    }

    for (int i = 0 ; i < len ; i ++){
        int ty = all[i].ty;
        int f  = all[i].f;
        int s  = all[i].s; 
        //cout << ty << " " << f << " " << s <<endl;
        int relation = goodState(ty , f , s);
        if (relation == -1){
            fakeNum++;
        }
        else{
            if (!merge(f-1,s-1,relation)){
                fakeNum++;
            }
        }
    }
    //sort(all.begin(), all.end());
    //std::vector<int>::iterator nown = unique(all.begin(), all.end());
    //all.erase(nown,all.end());
    //re = 0;
}

void calc(){

}

void output(){
    cout << fakeNum;
    // cout <<num << " "<< len << endl;

    // for (int i = 0 ; i < d.size() ; i ++){
    //         cout << "1 "<<" " <<d[i].first << " " << d[i].second <<endl;
    // }
    // for (int i = 0 ; i < w.size() ; i ++){
    //         cout << "2 "<<" " <<w[i].first << " " << w[i].second <<endl;
    // }
    // for (int i = 0 ; i < all.size() ; i ++){
    //         cout << all[i]<< " ";
    // }
}

int main(){
    input();
    calc();
    output();
    return 0;
}      

測例生成器：

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;

int N=50000,K = 100000;

int main(){
    srand(unsigned(time(0)));
    cout << N <<  " " << K << endl;
    for (int i = 0 ; i < K ; i++){
        cout << rand()%2+1 << " " << rand()%int(N+double(N)*0.01)+1<< " " << rand()%int(N+double(N)*0.01)+1<<endl;
    }
    
}