C++(g++ 7.5.0) 解法, 执行用时: 17ms, 内存消耗: 7072K, 提交时间: 2023-07-25 18:56:04

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define N 200010

struct node{
	int fa,re;
};

int n,q,m,num,a[N],b[N];
string s[N]; 
map<int,node>p;

int root(int x){
	if(x==p[x].fa)return x;
	int tmp=p[x].fa;
	p[x].fa=root(tmp);
	p[x].re=(p[x].re+p[tmp].re)%2;
	return p[x].fa;
}

void solve(){
	cin>>n>>q;
	for(int i=1;i<=q;i++){
		cin>>a[i]>>b[i]>>s[i];
		a[i]--;
		p[a[i]].re=0,p[a[i]].fa=a[i];
		p[b[i]].re=0,p[b[i]].fa=b[i];
	}
	for(int i=1;i<=q;i++){
		int x,y,z;
		x=a[i];
		y=b[i];
		z=s[i][0]=='o'?1:0;
		int rx=root(x),ry=root(y);
		if(rx!=ry){
			p[rx].fa=ry;
			p[rx].re=(p[x].re+p[y].re+z)%2;
		}else{
			if(p[x].re!=(p[y].re+z)%2){
				cout<<i-1;
				return ;
			}
		}
	}
	cout<<q;
}

signed main(){
 	ios::sync_with_stdio(0);
	cin.tie(0); 
	solve();
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 12ms, 内存消耗: 996K, 提交时间: 2020-03-08 20:21:02

#include<iostream>
#include<cstring>
#include<map>
#include<cstdio>
using namespace std;
map<int,int>fa;
map<int,int>cnt;
int findfather(int v)
{
    if(fa[v]==0||fa[v]==v)return fa[v]=v;
    int pp=findfather(fa[v]);
    cnt[v]=cnt[v]+cnt[fa[v]];
    cnt[v]&=1;
    fa[v]=pp;
    return pp;
}
int main()
{
    int x,n;
    cin>>x>>n;
    for(int i=1;i<=n;i++)
    {
        int p,q;
        char r[15]={0};
        scanf("%d%d%s",&p,&q,r);
        q++;
        int flg=1;
        if(r[0]=='e')flg=0;
        int p1=findfather(p),q1=findfather(q);
        if(p1==q1)
        {
            if(cnt[p]!=((cnt[q]+flg)&1))printf("%d\n",i-1);
            else continue;
            return 0;
        }else
        {
            cnt[q1]=(cnt[q]!=flg);
            fa[q1]=p;
        }
    }
    printf("%d\n",n);
    return 0;
}

Python3 解法, 执行用时: 104ms, 内存消耗: 5508K, 提交时间: 2023-05-22 15:30:48

n = int(input())
n += 1
t = int(input())

root = {}

def find(x):
    if x!=root[x]:
        root[x] = find(root[x])
    return root[x]

def union(a, b):
    root[find(a)] = find(b)

ans = t
for i in range(t):
    a, b, c = input().split()
    a, b = int(a), int(b)
    if b not in root:
        root[b] = b
        root[b+n] = b+n
    if a-1 not in root:
        root[a-1] = a-1
        root[a-1+n] = a-1+n
    if c=='even':
        if find(a-1)==find(b+n) or find(a-1+n)==find(b):
            ans = i
            break
        else:
            union(a-1, b)
            union(a-1+n, b+n)
    else:
        if find(a-1)==find(b) or find(a-1+n)==find(b+n):
            ans = i
            break
        else:
            union(a-1, b+n)
            union(a-1+n, b)
            
print(ans)

C++ 解法, 执行用时: 9ms, 内存消耗: 524K, 提交时间: 2022-01-07 11:54:01

#include<bits/stdc++.h>
using namespace std;
int fa[20001],m,n,a[20001],t;
char st[20001];
struct node{int l,r,ty;}que[10001];
int ft(int x){return x==fa[x]?x:fa[x]=ft(fa[x]);}
int main(){
	cin>>m>>n;
    for(int i=1;i<=n;i++)cin>>que[i].l>>que[i].r>>st,que[i].ty=(st[0]=='o'?1:0),a[++t]=que[i].l-1,a[++t]=que[i].r;
    sort(a+1,a+t+1);
    m=unique(a+1,a+t+1)-a-1;
    for(int i=1;i<=2*m;i++)fa[i]=i;
    for(int i=1;i<=n;i++){
        int x=lower_bound(a+1,a+m+1,que[i].l-1)-a,y=lower_bound(a+1,a+m+1,que[i].r)-a,xx=x+m,yy=y+m;
        if(que[i].ty==1){if(ft(x)==ft(y))cout<<i-1,exit(0);fa[ft(x)]=ft(yy);fa[ft(xx)]=ft(y);}
        else{if(ft(x)==ft(yy))cout<<i-1,exit(0);fa[ft(x)]=ft(y);fa[ft(xx)]=ft(yy);}
    }
    cout<<n;
    return 0;
}