做题感悟：做完这题第一感觉就是并查集的题只要一加深一下就不会了
。
解题思路：
给你长度为 n 的 0 和 1 组成的字符串，然后问给你许多条件 x ~ y 之间（包括x , y ）有奇数个 1 或偶数个 1 ，基于以前的条件判断是否正确（只要存在一种情况正确就可以）.首先对于 x ~ y 如果你知道 x~z 的奇偶性（即 1 的个数的奇偶性）同时知道 y~z 的奇偶性，从而就可以判断 x~y 的奇偶性。
例如：x ~ z 为偶数个（用 0 表示），y ~ z 为奇数个（用 1 表示），那么x ~ y 必定奇数个。这样可以用异或来表示： T[x].relation ^ T[y].relation .
判断时：如果 find( x ) = = find( y ) 只要异或一下看是否等于输入的奇偶性就可以了。 否则，合并 x y 所在集合。
因为 n 很大开数组开不下，而m可以开的下，so 用map 离散化。
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
const double PI = 3.1415926 ;
const int INF = 99999999 ;
const int MX =100006 ;
int n,mx ;
struct node
{
int parent,relation ;
}T[MX] ;
void init() // 初始化
{
for(int i=0 ;i<MX ;i++)
{
T[i].parent=i ;
T[i].relation=0 ;
}
}
int find(int x) // 寻找父亲 同时更新节点信息
{
if(T[x].parent!=x)
{
int temp=T[x].parent ;
T[x].parent=find(temp) ;
T[x].relation=T[x].relation^T[temp].relation ;
return T[x].parent ;
}
return T[x].parent ;
}
int main()
{
int x,y,r=0,i,c ;
char s[20] ;
map<int,int>m ;
scanf("%d%d",&n,&mx) ;
init() ;
for(i=1 ;i<=mx ;i++)
{
scanf("%d%d%s",&x,&y,s) ;
if(s[0]=='e')
c=0 ;
else c=1 ;
x-- ;
if(m.find(x)==m.end()) // 因为 n 很大 so 用map离散化
m[x]=r++ ;
if(m.find(y)==m.end())
m[y]=r++ ;
x=m[x] ;
y=m[y] ;
int ax=find(x) ; // 寻找父亲
int ay=find(y) ;
if(ax==ay) // 父亲相同
{
if((T[x].relation^T[y].relation)!=c)
break ;
}
else
{
T[ay].parent=ax ;
T[ay].relation=T[x].relation^T[y].relation^c ;
}
}
printf("%d\n",i-1) ;
return 0 ;
}