扩展域并查集(类似拆点?)
先合并再判断可以不用分类讨论,直接判断点自己与自己有无矛盾
#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=20010,base=N/2;
typedef pair<int,int> PII;
unordered_map<int,int> S;
int n,m;
int p[N],d[N];
int get(int x)
{
if(!S.count(x))S[x]=++n;
return S[x];
}
int find(int x)
{
//cout<<x<<" "<<p[x]<<endl;
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
bool check(int x,int fa)
{
if(x==p[x])return 0;
if(x==fa+base||x+base==fa)return 1;
return check(p[x],fa);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
n=0;
int res=m;
for(int i=0; i<N; i++)p[i]=i;
for(int i=1; i<=m; i++)
{
int a,b;
string s;
cin>>a>>b>>s;
int t=(s=="odd");
a=get(a-1),b=get(b);
int pa=find(a),pb=find(b);
int ba=find(a+base),bb=find(b+base);
if(t==1)p[pb]=ba,p[bb]=pa;
else p[pb]=pa,p[bb]=ba;
if(check(pa,pa))
{
res=i-1;
break;
}
}
cout<<res<<endl;
return 0;
}