并查集+带权
C++ 代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> m;
int t,n;
const int N = 2e4+5;
int p[N],d[N];
int get(int x) {
if(m[x]==0) return m[x] = ++n;
return m[x];
}
int find(int x) {
if(p[x]!=x) {
int t = find(p[x]);
d[x] = (d[x]+d[p[x]])%2;
p[x] = t;
return t;
}
return p[x];
}
int main() {
int res = 0;
cin>>n>>t;
n = 0;
for(int i = 0; i < N; ++i) p[i] = i;
res = t;
for(int i = 1; i<= t; ++i) {
int x,y;
string s;
cin>>x>>y>>s;
x = get(x-1),y = get(y);
int xx = find(x),yy = find(y);
if(s == "even") {
if(xx==yy) {
if((d[x]+d[y])%2==1) {
res = i - 1;
break;
}}
else {
d[xx] = d[x] + d[y];
p[xx] = yy; }
}
else {
if(xx==yy) {
if((d[x]+d[y])%2==0) {
res = i-1;
break;
}}
else {
d[xx] = d[x]+d[y]+1;
p[xx] = yy;
}
}
}
cout<<res;
}