并查集

边带权

只存在两种关系，分别是奇偶性相同，奇偶性不同，使用边带权的并查集进行统计时，集合内的每一个元素，与fa[i]的关系及与fa[fa[i]]的关系……，求和后对关系总数取模，得到的关系是与集合代表元素的关系

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 1e5 + 5;
int n, m;
int fa[N], d[N], cnt;
unordered_map<int, int>h;

int discrete(int x)
{
    if(h.count(x) == 0) h[x] = ++cnt;
    return h[x];
}

int find(int a) 
{
    if(fa[a] == a) return a;
    int root = find(fa[a]);
    d[a] ^= d[fa[a]];
    return fa[a] = root;
}

void merge(int a, int b, int ans)
{
    int x = find(a), y = find(b);
    d[x] = d[a] ^ d[b] ^ ans;
    fa[x] = y;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < N; i++) fa[i] = i;

    for(int i = 1; i <= m; i++)
    {
        int l, r, ans;
        string s;
        cin >> l >> r >> s;
        l = discrete(l - 1);
        r = discrete(r);
        if(s[0] == 'e') ans = 0;
        else ans = 1;
        int x = find(l), y = find(r);
        if(x != y)
        {
            merge(l, r, ans);   
        }
        else
        {
            if(d[l] ^ d[r] != ans)
            {
                cout << i - 1 << endl;
                return 0;
            }
        }
    }

    cout << m << endl;

    return 0;
}

扩展域

将关系的域进行分割，使域变得单一，便于统计，校对答案时，需处理各个域之间的关系

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 1e4 + 5;
int n, m, idx;
unordered_map<int, int>h;
int f[2 * N];

int discrete(int x)
{
    if(h.find(x) == h.end()) h[x] = ++idx;
    return h[x];
}

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i < 2 * N; i++) f[i] = i;

    for(int i = 0; i < m; i++)
    {
        int l, r, ans;
        string s;
        cin >> l >> r >> s;
        l = discrete(l - 1);
        r = discrete(r);
        int le = l, re = r;
        int lo = l + N, ro = r + N;
        int plo = find(lo), pro = find(ro);
        int ple = find(le), pre = find(re);
        if(s[0] == 'e')
        {

            if(plo == pre)
            {
                cout << i << endl;
                return 0;
            }
            f[plo] = pro;
            f[ple] = pre;
        }
        else 
        {
            if(plo == pro)
            {
                cout << i << endl;
                return 0;
            }
            f[plo] = pre;
            f[ple] = pro;
        }
    }

    cout << m << endl;

    return 0;
}