這是并查集最后一題，據(jù)說也是最經(jīng)典的一題。經(jīng)常前面幾題的訓(xùn)練，這題的思路很快
就能想出來了。只需要對(duì)每個(gè)節(jié)點(diǎn)附加一個(gè)信息表示離根節(jié)點(diǎn)的距離，并且距離是模3循環(huán)的。
注意合并時(shí)候保持距離變化的正確性。而且合并有2種情況，距離相同合并和距離不同合并。
分別對(duì)應(yīng)于題目描述中的1和2操作。
關(guān)鍵還是FindSet里面對(duì)距離nDis數(shù)組里面的修改，前面一直寫錯(cuò)這個(gè)，wa了好幾次，還是
看隊(duì)友代碼才一眼發(fā)現(xiàn)我又把這里寫錯(cuò)了。。。當(dāng)前距離的更新還是等于當(dāng)前距離加上前一個(gè)
節(jié)點(diǎn)的距離再模3，類似于前面幾題的更新方法。
這種將有關(guān)系的節(jié)點(diǎn)放在一個(gè)并查集里面，再給每個(gè)節(jié)點(diǎn)附加其它信息描述其它關(guān)系的做法，
確實(shí)比較有效。。。并查集是應(yīng)用于不相交集合的數(shù)據(jù)結(jié)構(gòu)，看來某個(gè)時(shí)候卻有妙用啊。。。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
const int MAX = 50010;
int nN, nK;
int nSets[MAX];
int nDis[MAX];
void MakeSets(
int nN)
{
for (
int i = 1; i <= nN; ++i)
{
nSets[i] = i;
nDis[i] = 0;
}
}
int FindSet(
int nI)
{
if (nSets[nI] != nI)
{
int nPre = nSets[nI];
nSets[nI] = FindSet(nSets[nI]);
nDis[nI] = (nDis[nPre] + nDis[nI]) % 3;
}
return nSets[nI];
}
int main()
{
int nAns = 0;
int nOper, nX, nY;
scanf("%d%d", &nN, &nK);
MakeSets(nN);
while (nK--)
{
scanf("%d%d%d", &nOper, &nX, &nY);
if (nX > nN || nY > nN || nOper == 2 && nX == nY)
{
++nAns;
}
else {
if (nOper == 1)
{
int nA = FindSet(nX);
int nB = FindSet(nY);
if (nA == nB)
{
if (nDis[nX] != nDis[nY])
{
++nAns;
}
}
else {
nSets[nB] = nA;
nDis[nB] = (nDis[nX] - nDis[nY] + 3) % 3;
}
}
else {
int nA = FindSet(nX);
int nB = FindSet(nY);
if (nA == nB)
{
if ((nDis[nX] + 1) % 3 != nDis[nY])
{
++nAns;
}
}
else {
nSets[nB] = nA;
nDis[nB] = (nDis[nX] + 1 - nDis[nY] + 3) % 3;
}
}
}
}
printf("%d\n", nAns);
return 0;
}