前缀和思想简化 + 带权并查集

处理逻辑：先判断有没有矛盾，没有则补充距离信息

带权并查集的思想：只要两个元素在一个集合里面，通过它们与根节点的距离就能知道它们的相对关系,所以都要维护距离d[]数组

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 20010;

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

int get(int x)
{
    if(S.count(x) == 0) 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<N;i++) p[i] =i;

    int res = m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        string type;

        cin >> a >> b >> type;
        a = get(a-1), b= get(b);

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

        if(type == "even") // 它说它们是同类
        {
            if(pa==pb) // 先判定有无矛盾
            {
                if( ((d[a] - d[b]) % 2 + 2) % 2  != 0  )
                {
                    res = i-1;
                    break;
                }
            }
            else if(pa!=pb) // 无矛盾后补充信息
            {
                p[pa]=pb;
                d[pa] = d[b] - d[a];
            }
        }

        else // 它说它们是异类
        {
             if(pa==pb) // 先判定有无矛盾
            {
                if( ((d[a] - d[b]) % 2 + 2) % 2  == 0  )
                {
                    res = i-1;
                    break;
                }
            }
            else if(pa!=pb) // 无矛盾后补充信息
            {
                p[pa]=pb; // 即使是异类也要把它们归到一个集合里面给后面判断提供条件，也是带权并查集的精髓
                d[pa] = d[b] + 1 - d[a]; // 这里正负都可，因为上面取模保证非负
            }
        }
    }

    cout<<res<<endl;

    return 0;
}

用 t 来合并两种情况的讨论，是对上面的简化

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 20010; // 离散化，左右端点，两倍的 10000

int n,m; // n 用来离散化分配下标
int p[N], d[N];
unordered_map<int,int> S;

int get(int x)
{
    if(S.count(x) == 0) 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=0;i<N;i++) p[i] = i;

    int res=m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        string type;
        cin >> a >> b >> type;
        a=get(a-1), b=get(b); // 前缀和思想

        int t=0;
        if(type=="odd") t=1; // 异类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; // 模2加的意义下就是异或
            // d[pa] = d[b] - d[a] + t; // 用这句话比较直观：这里两种情况一起讨论，t 为合并结果，异类要加上
        }
    }

    cout<<res<<endl;

    return 0;
}

扩展域写法

思想：结点不是表示元素，而是表示一类条件

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 40010, Base = N /2; // 离散化，左右端点，两倍的 10000,扩展域，再扩展2倍

int n,m; // n 用来离散化分配下标
int p[N];
unordered_map<int,int> S;

int get(int x)
{
    if(S.count(x) == 0) S[x] = ++ n; // 分配一个下标
    return S[x];
}

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

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

    for(int i=0;i<N;i++) p[i] = i;

    int res=m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        string type;
        cin >> a >> b >> type;
        a=get(a-1), b=get(b); // 前缀和思想

        if(type=="even")
        {
            if(find(a + Base) == find(b)) // 这样表明是异类，不满足要求
            {
                res = i - 1;
                break;
            }
            p[find(a)] = find(b);
            p[find(a + Base)] = find(b + Base);
        }
        else
        {
            if(find(a) == find(b))
            {
                res = i-1;
                break;
            }
            p[find(a + Base)] = find(b);
            p[find(a)] = find(b + Base);
        }

    }

    cout<<res<<endl;

    return 0;
}