1734.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1734 on 2006-07-01 at 17:52:47 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int SN = 10240;

class UFSet {
private:
	int parent[SN], rank[SN];
public:
	void make() { memset(parent, -1, sizeof(parent)); memset(rank, 0, sizeof(rank)); }
	pii find(int);
	void unionSet(int, int, int);
};
pii UFSet::find(int x) {
	if(parent[x] == -1) return pii(x, 0);
	pii t = find(parent[x]);
	parent[x] = t.first; rank[x] = (rank[x]+t.second)&1;
	return pii(parent[x], rank[x]);
}
void UFSet::unionSet(int x, int y, int v) {
	pii pX = find(x), pY = find(y);
	parent[pX.first] = pY.first;
	rank[pX.first] = (v-pX.second+pY.second)&1;
}

class Equ {
public:
	int a, b, v;
	void make();
};
void Equ::make() {
	char val[8];
	scanf("%d %d %s", &a, &b, &val);
	v = (val[0] == 'o'); a--;
}

int disperse(int*, int);

int main()
{
	UFSet ufs;
	Equ e[SN>>1];
	int n, s[SN], i;
	
	while(scanf("%*d %d", &n) != EOF) {
		ufs.make();
		for(i = 0; i < n; i++) {
			e[i].make();
			s[2*i] = e[i].a; s[2*i+1] = e[i].b;
		}
		int sn = disperse(s, 2*n);
		for(i = 0; i < n; i++) {
			e[i].a = lower_bound(s, s+sn, e[i].a)-s; e[i].b = lower_bound(s, s+sn, e[i].b)-s;
			pii ap = ufs.find(e[i].a), bp = ufs.find(e[i].b);
			if(ap.first != bp.first) ufs.unionSet(e[i].b, e[i].a, e[i].v);
			else if((bp.second-ap.second-e[i].v)%2 != 0) break;
		}
		printf("%d\n", i);
	}
	
	return 0;
}

int disperse(int *s, int n)
{
	int i, sn = 1;
	sort(s, s+n);
	for(i = 1; i < n; i++)
		if(s[i] != s[i-1]) s[sn++] = s[i];
	return sn;
}