离散化&并查集

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int N=20005;
int n,m;
int fa[N], d[N];
map<int, int> S;

inline int get(int x){ // 离散化元素
    if(!S.count(x)) S[x]=++n;
    return S[x];
}

inline int find(int x){
    if(x!=fa[x]){
        int root=find(fa[x]);
        d[x]+=d[fa[x]];
        fa[x]=root;
    }
    return fa[x];
}

int main(){
    cin>>n>>m;
    n=0;
    for(int i=0; i<N; ++i) fa[i]=i;
    int ans=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;
        int pa=find(a), pb=find(b);
        if(pa==pb){
            if(((d[a]+d[b])%2+2)%2!=t){
                ans=i-1;
                break;
            }
        }
        else{
            fa[pa]=pb;
            d[pa]=d[a]^d[b]^t;
        }
    }
    cout<<ans<<endl;
    return 0;
}