Parity game(并查集)

题目链接：https://ac.nowcoder.com/acm/problem/51097

题意描述

输入给出了多组区间[xi,yi]中数字1的数量的奇偶性，要求我们根据已有的条件判断该下一数据是否能成立，若能成立则将其纳入条件，反之输出该条件的编号。

解析

对于已有条件我们可以这样考虑，将区间[xi,yi]中数字1的数量的奇偶性转换为区间[0,xi-1]与区间[xi,yi]中数字1的奇偶性是否相同。

开一个unordered_map维护一个并查集，并查集分为两部分，一部分为奇数个1的前缀和，另一部分为偶数个1前缀和，由于从第一组数据开始就形成两种可能性，分别形成两组集合，若某组区间两前缀和所属的集合不符合数据奇偶性的描述，输出该条件的编号即可。

#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int>fa;
int find(int x){
    return x==fa[x]? x : fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int main(){
    int len;cin>>len;
    int q,ans;cin>>q;ans=q;
    len++;//区分奇偶
    for(int i=0;i<q;i++){
        int x,y;cin>>x>>y;
        if(!fa.count(y))fa[y+len]=y+len,fa[y]=y;//一定要判断是否出现过
        if(!fa.count(x-1))fa[x+len-1]=x+len-1,fa[x-1]=x-1;//同上
        string s;cin>>s;
        if(s=="even"){
            if(find(x-1)==find(y+len)||find(x+len-1)==find(y)){//两个取一个即可，二者等价
                ans=i;
                break;
            }else{
                merge(x-1,y);
                merge(x-1+len,y+len);
            }
        }else{
           if(find(x-1)==find(y)||find(x-1+len)==find(y+len)){
               ans=i;
               break;
           }else{
               merge(x-1,y+len);
               merge(x-1+len,y);
           }
        }
    }
    cout<<ans<<endl;
    return 0;
}