二分图+二分

import java.util.*;

class Main{

    static int N, M, idx;
    static int[] h, next, e, w, col, ls, rs, op;
    static HashMap<Integer, Integer> map;

    static int unique(int[] a){
        int offset = 0;
        for(int i=1; i<a.length; i++){
            if(a[i]==a[i-1]){
                offset++;
                continue;
            }else if(offset>0) a[i-offset] = a[i];
        }
        return a.length - offset;
    }

    static void add(int a, int b, int c){
        e[idx] = b; w[idx] = c; next[idx] = h[a]; h[a] = idx++;
    }

    static boolean DFS(int x){
        for(int i=h[x]; i!=-1; i=next[i]){
            int y = e[i];
            if(col[y]==0){
                if(w[i]==0) col[y] = col[x];
                else col[y] = -col[x];
                if(!DFS(y)) return false;
            }else{
               boolean t =  (w[i]==0&&col[x]==col[y])||(w[i]==1&&col[x]==-col[y]);
               if(!t) return false;
            }
        }
        return true;
    }

    static boolean check(int mid){

        Arrays.fill(h, -1); 
        col = new int[2*M];
        idx = 0;
        boolean flag = true;

        for(int i=0; i<=mid; i++){
            int a = map.get(ls[i]);
            int b = map.get(rs[i]);
            int d = op[i];
            add(a, b, d); 
            add(b, a, d);
        }

        for(int i=0; i<h.length; i++){
            if(col[i]==0){
                col[i] = 1;
                if(!DFS(i)){
                    flag = false;
                    break;
                } 
            }
        }

        return flag;
    }

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);
        N = in.nextInt(); M = in.nextInt();
        int[] a;

        ls = new int[M]; rs = new int[M]; op = new int[M];
        a = new int[2*M];

        for(int i=0, j=0; i<M; i++){
            int p, q;
            p  = in.nextInt(); q = in.nextInt();
            if(q<p){
                int t = p;
                p = q;
                q = t;
            }
            ls[i] = p - 1; rs[i] = q;
            op[i] = in.next().equals("even")?0:1;
            a[j++] = ls[i]; a[j++] = rs[i];
        }

        Arrays.sort(a);

        int len = unique(a);
        map = new HashMap<>();
        for(int i=0; i<len; i++) map.put(a[i], i);
        h = new int[len]; e = new int[2*M]; next = new int[2*M]; w = new int[2*M];

        int l, r;
        l = 0; r = M-1;

        if(M==0||check(M-1)){
            System.out.println(M);
            return;
        }
        while(l<r){
            int mid = l + r + 1 >> 1;
            if(check(mid)) l = mid;
            else r = mid - 1;
        }
        System.out.println(l+1);
    }
}

带权并查集

import java.util.*;

class Main{

    static int N, M;
    static int[] f, d;

    static int unique(int[] a){
        int offset = 0;
        for(int i=1; i<a.length; i++){
            if(a[i]==a[i-1]){
                offset++;
                continue;
            }else if(offset>0)
                a[i-offset] = a[i];
        }
        return a.length - offset;
    }

    static int find(int x){
        if(f[x]!=x){
            int fa = find(f[x]);
            d[x] ^= d[f[x]];
            f[x] = fa;
        }
        return f[x];
    }

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);
        N = in.nextInt(); M = in.nextInt();
        int[] ls, rs, ans, a;
        ls = new int[M]; rs = new int[M]; ans = new int[M]; a = new int[2*M];
        for(int i=0, j=0; i<M; i++){
            ls[i] = in.nextInt()-1; rs[i] = in.nextInt(); ans[i] = in.next().equals("even")?0:1;
            a[j++] = ls[i]; a[j++] = rs[i];
        }
        Arrays.sort(a);
        int len = unique(a);
        HashMap<Integer, Integer> map = new HashMap<>();
        f = new int[len+1];
        d = new int[len+1];
        for(int i=1; i<=len; i++){
            map.put(a[i-1], i);
            f[i] = i;
        } 
        for(int i=0; i<M; i++){

            int l = map.get(ls[i]);
            int r = map.get(rs[i]);
            int p = find(l), q = find(r);
            if(p==q){

                int t = d[l]^d[r]^ans[i];
                //System.out.println(t);
                if(t!=0){
                    System.out.println(i);
                    return;
                }
            }else{

                d[p] ^= d[l]^d[r]^ans[i];
                f[p] = q;

            }
        }
        System.out.println(M);
    }
}