这几天做了些并查集的题目，其中有一些简单题就是直接套模板，没什么可以思考的。但今天做的两道题就稍微有些难度了，只有真正理解了“并”和“查”的过程才有解题的思路。
思路：
告诉你[a,b]之间1个数的奇偶情况，那么你就可以在a-1和b之间连一条边，权值就是其奇偶情况。这样一来，比如[1,2]和[3,4]的情况已知，[1,4]的情况也就知道了。当题目给出[a,b]的情况时，首先分别从a和b往上找，找到他们的根r1和r2，如果r1 != r2，表示a,b之间的奇偶情况还不确定，就将r1和r2之间连起来，根据a到r1的权值、b到r2的权值和题目所给的奇偶情况，设置r1和r2之间的权值，以符合题目要求。若r1 == r2，则表示[a,b]之间情况已确定，根据a到r1的权值和b到r2的权值，就可以判断题目所给的[a,b]的情况是否为真。
其实当时做的时候，还不是很懂，但没想到稀里糊涂的就AC了。推荐一下这个网页：http://hi.baidu.com/fandywang_jlu/blog/item/b49e40893ddbb0b00f244485.html，这里面介绍并查集挺详细的，还有不少推荐题目，有些还不会做。：P
代码：
#include <iostream>
#include <map>
using namespace std;
const int MAX = 10005;
int n, p;
int pre[MAX];
int parity[MAX]; //i到目前集合的根的奇偶情况
map<int, int> numIndex; //用于离散化
int Find (int x)
{
if ( pre[x] == -1 )
return x;
int f;
f = Find(pre[x]);
parity[x] = (parity[x] + parity[pre[x]]) % 2; //此时pre[x]已指向最终的集合的根
pre[x] = f;
return f;
}
bool Query (int x, int y, int odd)
{
int r1, r2;
r1 = Find(x);
r2 = Find(y);
if ( r1 == r2 )
{
if ( (parity[x] + parity[y]) % 2 == odd )
return true;
else
return false;
}
else //只是将r1接到r2下面，这边还可以优化
{
pre[r1] = r2;
parity[r1] = (parity[x] + parity[y] + odd) % 2;
return true;
}
}
void Solve ()
{
int i, x, y, index, idx1, idx2, odd;
char s[10];
scanf("%d%d", &n, &p);
index = 0;
for (i=0; i<p; i++)
{
scanf("%d%d%s", &x, &y, &s);
x --;
if ( numIndex.find(x) == numIndex.end() )
numIndex[x] = index ++;
idx1 = numIndex[x];
if ( numIndex.find(y) == numIndex.end() )
numIndex[y] = index ++;
idx2 = numIndex[y];
if ( strcmp(s, "odd") == 0 )
odd = 1;
else
odd = 0;
if ( Query(idx1, idx2, odd) == false )
{
break;
}
}
printf("%d\n", i);
}
void Init ()
{
memset(pre, -1, sizeof(pre));
}
int main ()
{
Init();
Solve();
return 0;
}