莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 偶数：说明 s[b] 和 s[a-1] 奇偶性相同；奇数：说明 s[b] 和 s[a-1] 奇偶性不同
2. 如果在同一集合就判断他们是否有矛盾，否则合并集合并维护到根节点的距离

可参考： 食物链

#include<bits/stdc++.h>

using namespace std;

const int N = 10010;

int n,m;
int p[N],d[N];
unordered_map<int,int> S;

//离散化操作
int get(int x)
{
    if(!S.count(x)) S[x]=++n;
    return S[x];
}

int find(int x)
{
    if(p[x]!=x)
    {
        int root=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
    }

    return p[x];
}

int main()
{
    cin>>n>>m;
    n=0;

    for(int i=1;i<=m*2;i++) p[i]=i;

    int res=m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        string op;
        cin>>a>>b>>op;
        a=get(a-1),b=get(b);

        int t=0;
        if(op=="odd") t=1;

        int pa=find(a),pb=find(b);

        //在同一集合
        if(pa==pb)
        {
            //有矛盾
            if(((d[a]+d[b])%2+2)%2!=t)
            {
                res=i-1;
                break;
            }
        }

        //不在同一集合，合并集合
        else 
        {
            p[pa]=pb;
            d[pa]=d[a]+d[b]+t;
        }
    }

    cout<<res<<endl;

    return 0;
}