這幾天做了些并查集的題目，其中有一些簡(jiǎn)單題就是直接套模板，沒什么可以思考的。但今天做的兩道題就稍微有些難度了，只有真正理解了“并”和“查”的過程才有解題的思路。
思路：
告訴你[a,b]之間1個(gè)數(shù)的奇偶情況，那么你就可以在a-1和b之間連一條邊，權(quán)值就是其奇偶情況。這樣一來，比如[1,2]和[3,4]的情況已知，[1,4]的情況也就知道了。當(dāng)題目給出[a,b]的情況時(shí)，首先分別從a和b往上找，找到他們的根r1和r2，如果r1 != r2，表示a,b之間的奇偶情況還不確定，就將r1和r2之間連起來，根據(jù)a到r1的權(quán)值、b到r2的權(quán)值和題目所給的奇偶情況，設(shè)置r1和r2之間的權(quán)值，以符合題目要求。若r1 == r2，則表示[a,b]之間情況已確定，根據(jù)a到r1的權(quán)值和b到r2的權(quán)值，就可以判斷題目所給的[a,b]的情況是否為真。
其實(shí)當(dāng)時(shí)做的時(shí)候，還不是很懂，但沒想到稀里糊涂的就AC了。推薦一下這個(gè)網(wǎng)頁(yè)：http://hi.baidu.com/fandywang_jlu/blog/item/b49e40893ddbb0b00f244485.html，這里面介紹并查集挺詳細(xì)的，還有不少推薦題目，有些還不會(huì)做。：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; //此時(shí)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下面，這邊還可以優(yōu)化
{
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;
}