奇偶游戏

各种找矛盾的题..
下面用种比较好的算法写吧,不用扩展域,权值并查集.
怎么权值查并集呢?首先和上个题目一样,用一个d[x]表示x到根节点的距离.假如距离为偶数就表示同一面.奇数就表示对立面.

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5;
int n,m;
unordered_map<int,int>s;
int fa[N],d[N];
int find(int x)
{
    if(fa[x]!=x)
    {
        int root=find(fa[x]);
        d[x]+=d[fa[x]];
        fa[x]=root;
    }
    return fa[x];
}

int get(int x)
{
    if(s.count(x)==0) s[x]=++n;
    return s[x];
}

int main()
{
    for(int i=1;i<=N-5;i++) fa[i]=i;
    cin>>n>>m;
    int ans=m;
    n=0;
    for(int i=1;i<=m;i++)
    {
        int a,b;string c;
        cin>>a>>b>>c;
        a=get(a-1);b=get(b);
        int pa=find(a);int pb=find(b);
        if(c=="even")//偶数
        {
            if(pa==pb)
            {
                if(((d[a]-d[b])%2+2)%2!=0)//有矛盾
                {
                    ans=i-1;
                    break;
                }
            }
            else
            {
                fa[pa]=pb;
                d[pa]=d[b]-d[a];
            }
        }
        else//奇数
        {
            if(pa==pb)
            {
                if(((d[a]-d[b])%2+2)%2==0)//有矛盾
                {
                    ans=i-1;
                    break;
                }
            }
            else
            {
                fa[pa]=pb;
                d[pa]=d[b]-d[a]+1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}