种类并查集

北京大学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;
    }
    
}