poj 1703 Find them, Catch them

点击打开链接poj 1703

思路: 简单带权并查集
分析:
1 题目要询问给定的x和y是否是同一个动物
2 我们假设如果不同，那么权值为1，否则为0。因此对于给定的x和y，那么如果x和y不在一个集合里面那么就是不确定，否则就可以根据rank来判断是什么关系

代码：

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

const int MAXN = 1e5+10;

int father[MAXN];
int rank[MAXN];

void init(int n){
    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(fa); 
        rank[x] += rank[fa];
        rank[x] %= 2;
    }
    return father[x];
}

void output(int x , int y , int fx , int fy){
    if(fx != fy)
        puts("Not sure yet.");
    else{
        if(rank[x] == rank[y])  
            puts("In the same gang.");
        else
            puts("In different gangs.");
    }
}

int main(){
    char ch;
    int x , y;
    int cas , n , m;
    scanf("%d" , &cas);
    while(cas--){
        scanf("%d%d%*c" , &n , &m);
        init(n); 
        while(m--){
            scanf("%c %d %d%*c" , &ch , &x , &y); 
            int fx = find(x);    
            int fy = find(y);    
            if(ch == 'A'){
                output(x , y , fx , fy);
            }
            else{
                if(fx != fy){
                    father[fx] = fy;
                    rank[fx] = (rank[y]+1-rank[x]+2)%2;
                }   
            }
        }
    }
    return 0;
}