离散化&并查集
Parity game
https://ac.nowcoder.com/acm/problem/106330
#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;
}
小鹏汽车AI面6人在聊
