poj 1182 食物链

点击打开链接 poj 1182

1思路：带权并查集
2分析：
1 对于这道题，我们可以用权值0表示两个动物是属于同类，用权值1表示两个动物是属于捕食关系，用权值2表示两个动物属于竞争关系。那么这样就可以利用带权并查集的关系，如果当前的输入的两个动物编号在同一个集合那么我们利用权值的关系就可以很快的判断出关系，如果不在同一个集合则合并。
2 注意对于rank要mod 3，这样rank数组的值才能够是0 1 2这三个值。还有如果在求rank的时候，它的值如果可能变为负数要通过加上3来保证值非负，如果值可能超过等于3就要mod 3，但是这不影响结果。
3 这一题只有一组，如果写成while(scanf("%d%d" , &n , &m) != EOF),则会WA。

4 判断关系的时候，如果是不同的集合那就合并，否则判断是否有rank[x] == (rank[y]+val)%3

3 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 50010;

int n , m , ans;
int father[MAXN];
int rank[MAXN];

void init(){
    ans = 0;
    memset(rank , 0 , sizeof(rank));
    for(int i = 1 ; i <= n ; i++)
        father[i] = i;
}

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

void solve(int mark , int x , int y){
    if(x > n || y > n){
        ans++;
        return;
    }
    int fx = find(x);
    int fy = find(y);
    int v = mark == 1 ? 0 : 1;
    if(fx != fy){
       father[fx] = fy;
       rank[fx] = (rank[y]+v-rank[x]+3)%3;
    }
    else{
       if(rank[x] != (rank[y]+v)%3)
         ans++;
    }
}

int main(){
    int mark , x , y;
    scanf("%d%d" , &n , &m);
    init();
    ans = 0;
    for(int i = 0 ; i < m ; i++){
        scanf("%d%d%d" , &mark , &x , &y);         
        solve(mark , x , y);
    }
    printf("%d\n" , ans);
    return 0;
}