POJ 1733

• 带权并查集
• 权值既可以通过异或来表示奇偶的数量，也可以直接存奇偶数量1 2,路径压缩的时候累加起来就行了
• 此题点的范围太大,需要离散化,注意输入的次数最多为5000,则最多有1e4个点，
• 带权并查集+离散化

  #include <iostream>
  #include <string.h>
  #include <string>
  #include <map>
  
  using namespace std;
  
  const int maxn = 1e4 + 5;
  int n,m;
  int pre[maxn];
  int rala[maxn];
  map<int,int> e;
  void init() {
  	memset(rala,0,sizeof rala);
  	for (int i=1; i<=maxn; i++) pre[i] = i;
  }
  int find(int x) {
  	int temp = pre[x];
  	if (x == pre[x]) return x;
  	pre[x] = find(pre[x]);
  	rala[x] ^= rala[temp];
  	return pre[x];
  }
  bool merge(int a,int b,int k) {
  	int ra = find(a);
  	int rb = find(b);
  	if (ra == rb) {
  		if ( (rala[a] ^ rala[b]) != k ) 
  			return 0;
  		else return 1;
  	}
  	pre[ra] = rb;
  	rala[ra] = rala[a] ^ rala[b] ^ k;
  	return 1;
  }
  int a,b;
  string s;
  int cnt;
  int main() {
  //	freopen("a.txt","r",stdin);
  	cin >> n >> m;
  	if (m==0) cout << m << endl;
  	init();
  	for (int i=1; i<=m; i++) {
  		cin >> a >> b >> s;
  		bool k;
  
  		b++;
  		if (s == "even")  k = 0;
  		else k = 1;
  		
  		map<int,int>::iterator it1,it2;
  		it1 = e.find(a);
  		if (it1 == e.end()) e[a]=cnt++;
  		it2 = e.find(b);
  		if (it2 == e.end()) e[b]=cnt++;
  		
  		if (!merge(e[a],e[b],k)) {
  			cout << i-1 << endl;
  			break;
  		}
  		else if (i == m ) cout << i << endl;
  	}
  	return 0;
  }