种类并查集

　　一般的并查集是维护属于同一种类的元素，对于属于不同种类的元素之间的关系没有记录。种类并查集就是同一集合中的元素是已经确定关系的（是否属于同一种类），然后加一个group数组，记录一下孩子和父亲是否属于同一种类，递推稍稍改一下就可以了。

poj1703：http://poj.org/problem?id=1703

题目大意：有n个罪犯，两个帮派，已知其中若干对两者属于不同帮派，求给定的罪犯是否属于同一帮派。

需要注意，给的两个罪犯可能已经在同一个集合里了，需要处理一下，不然就无限递归了。。。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1e5+5;
int p[maxn],group[maxn],n,m;
int Find(int x){
    if(p[x]==x)return x;
    int t=Find(p[x]);
    group[x]=group[x]==group[p[x]]?1:0;
    return p[x]=t;
}
void Unit(int a,int b){
    int x=Find(a),y=Find(b);
    if(x==y)return;
    p[x]=b;
    group[x]=1^group[a];
}
int Is_same(int a,int b){
    int x=Find(a),y=Find(b);
    if(x!=y)return -1;
    return group[a]==group[b];
}
int main(){
    int t,a,b;
    char c;
    scanf("%d",&t);
    while(t--){
        scanf("
%d%d",&n,&m);
        for(int i=0;i<n;i++){p[i]=i;group[i]=1;}
        for(int i=0;i<m;i++){
            scanf("
%c%d%d",&c,&a,&b);
            a--;b--;
            if(c=='D'){
                Unit(a,b);
            }else{
                int t=Is_same(a,b);
                if(t==-1)printf("Not sure yet.
");
                else if(t==0)printf("In different gangs.
");
                else if(t==1)printf("In the same gang.
");
            }
        }
    }
    return 0;
}

51nod 1204 Parity

分析：记前k个的和的奇偶性为f[k]，若[a,b]和为偶数，则f[a]==f[b]，否则f[a]！=f[b]，然后用种类并查集维护一下就可以了。

#include<iostream>
#include<string>
using namespace std;
const int maxn=100005;
int p[maxn],group[maxn],n,q;
int Find(int x){
    if(p[x]==x)return x;
    Find(p[x]);
    group[x]=group[p[x]]==group[x]?1:0;
    p[x]=Find(p[x]);
    return p[x];
}
int main(){
    cin>>n>>q;
    for(int i=0;i<=n;i++){p[i]=i;group[i]=1;}
    int a,b,ans=-1;
    char s[10];
    for(int i=0;i<q;i++){
        cin>>a>>b>>s;
        int x=Find(a-1),y=Find(b);
        if(s[0]=='e'){
            if(x==y&&group[a-1]!=group[b]&&ans==-1)
                ans=i+1;
            if(x!=y){
                p[x]=y;
                group[x]=group[a-1]==group[b]?1:0;
            }
        }else{
            if(x==y&&group[a-1]==group[b]&&ans==-1)
                ans=i+1;
            if(x!=y){
                p[x]=y;
                group[x]=group[a-1]==group[b]?0:1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}