R、parity game

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e5 + 50;

int n, m, fa[N], r[N];
map<int, int> mp;
int ans, cnt = 0;

int find (int x) {
    if (fa[x] == -1) return x;
    int pre = find (fa[x]);
    r[x] = (r[x] + r[fa[x]]) % 2;
    return fa[x] = pre;
}

bool Union (int u, int v, int w) {
    int fu = find (u);
    int fv = find (v);
    if (fu == fv)
        return (r[v] - r[u] + 2) % 2 != w;
    fa[fv] = fu;
    r[fv] = (-r[v] + w + r[u] + 2) % 2;
    return false;
}

signed main () {
    cin >> n >> m;
    memset (fa, -1, sizeof fa);
    memset (r, 0, sizeof r);
    ans = m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        char s[5];
        cin >> u >> v >> s;
        u--;
        if (mp.find (u) == mp.end ()) mp[u] = ++cnt;
        if (mp.find (v) == mp.end ()) mp[v] = ++cnt;
        int k = (int) (s[0] == 'o');
        if (ans == m && Union (mp[u], mp[v], k))
            ans = i - 1;
    }
    mp.clear ();
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;
int n, m, tot, res, b[100010], fa[100010];
#define int long long

struct node {
    int u, v;
    string op;
} a[100010];

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

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (nullptr), cout.tie (nullptr);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].u >> a[i].v;
        cin >> a[i].op;
        b[++tot] = a[i].u;
        b[++tot] = a[i].v;
    }
    sort (b + 1, b + 1 + tot);
    res = unique (b + 1, b + 1 + tot) - (b + 1);
    for (int i = 1; i <= m; i++) {  //STL实现离散化的三部曲
        a[i].u = lower_bound (b + 1, b + 1 + res, a[i].u - 1) - b;
        a[i].v = lower_bound (b + 1, b + 1 + res, a[i].v) - b;
    }
    for (int i = 1; i <= 2 * res; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        if (a[i].op == "even"){  //如果回答是偶数个
            if (find (a[i].u) == find (a[i].v + res) || find (a[i].u + res) == find (a[i].v)){  //判断奇偶性
                cout << i - 1 << " ";   //注意是i-1而不是i
                return 0;
            }
            fa[find (a[i].u)] = find (a[i].v);
            fa[find (a[i].u + res)] = find (a[i].v + res);
        } else {
            if (find (a[i].u) == find (a[i].v) || find (a[i].u + res) == find (a[i].v + res)){
                cout << i - 1;
                return 0;
            }
            fa[find (a[i].u)] = find (a[i].v + res);
            fa[find (a[i].u + res)] = find (a[i].v);
        }
    }
    cout << m << endl;
    return 0;
}