扩展域并查集

// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define xx first
#define yy second
// #define int ll
using namespace std;
using ll = long long;
using ld = long double;
using PII = pair<int, int>;
const int N = 1e4+7;
const int inf = 0x3f3f3f3f;
const int eps = 1e-8;
const int mod = 1e9+7;

int n, m, a[N], b[N], o[N], fa[N << 1];

inline int find(int x){
    if (x == fa[x]) return x;
    else return fa[x] = find(fa[x]);
}

void solve()
{ 
    cin >> n >> m;
    vector<int> v;
    for (int i = 1; i <= m; i ++){
        string s;
        cin >> a[i] >> b[i] >> s;
        a[i] --;
        if (s == "even") o[i] = 0;
        else o[i] = 1;

        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    n = v.size();
    for (int i = 0; i < n + n; i ++) fa[i] = i;
    for (int i = 1; i <= m; i ++){
        int x = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        int y = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
        if (!o[i]){
            int fx = find(x), fny = find(y + n);
            if (fx == fny){
                cout << i - 1 << '\n';
                return;
            }
            int fy = find(y), fnx = find(x + n);
            fa[fx] = fy;
            fa[fnx] = fa[fny];
        }
        else{
            int fx = find(x), fy = find(y);
            if (fx == fy){
                cout << i - 1 << '\n';
                return;
            }
            int fnx = find(x + n), fny = find(y + n);
            fa[fx] = fny;
            fa[fnx] = fy;
        }
    }
    cout << m << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt --) solve();
    return 0;
}

带权并查集

// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define xx first
#define yy second
// #define int ll
using namespace std;
using ll = long long;
using ld = long double;
using PII = pair<int, int>;
const int N = 1e4+7;
const int inf = 0x3f3f3f3f;
const int eps = 1e-8;
const int mod = 1e9+7;

int n, m, a[N], b[N], o[N], fa[N], d[N];

inline int find(int x){
    if (x == fa[x]) return x;
    int r = find(fa[x]);
    d[x] ^= d[fa[x]];
    return fa[x] = r;
}

void solve()
{ 
    cin >> n >> m;
    vector<int> v;
    for (int i = 1; i <= m; i ++){
        string s;
        cin >> a[i] >> b[i] >> s;
        a[i] --;
        if (s == "even") o[i] = 0;
        else o[i] = 1;

        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    n = v.size();
    for (int i = 0; i < n; i ++) fa[i] = i;
    for (int i = 1; i <= m; i ++){
        int x = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        int y = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
        int fx = find(x), fy = find(y);
        if (fx == fy){
            if ((d[x] ^ d[y]) != o[i]){
                cout << i - 1 << '\n';
                return;
            }
        }
        else{
            fa[fx] = fy;
            // 这里很妙d[fx] = d[x] ^ o[i] ^ d[y]表示奇偶性从x传递到fx到y到dy，最终得到fx和fy的奇偶性关系。
            // 从 o[i] = d[fx] ^ d[x] ^ d[y] 推出来的。
            d[fx] = d[x] ^ o[i] ^ d[y];
        } 
    }
    cout << m << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt --) solve();
    return 0;
}