poj 1182 食物鏈 並查集

這是並查集最後一題，據說也是最經典的一題。經常前面幾題的訓練，這題的思路很快
就能想出來了。只需要對每個節點附加一個信息表示離根節點的距離，並且距離是模3循環的。
   注意合並時候保持距離變化的正確性。而且合並有2種情況，距離相同合並和距離不同合並。
分別對應於題目描述中的1和2操作。
   關鍵還是FindSet裡面對距離nDis數組裡面的修改，前面一直寫錯這個，wa了好幾次，還是
看隊友代碼才一眼發現我又把這裡寫錯了。。。當前距離的更新還是等於當前距離加上前一個
節點的距離再模3，類似於前面幾題的更新方法。
   這種將有關系的節點放在一個並查集裡面，再給每個節點附加其它信息描述其它關系的做法，
確實比較有效。。。並查集是應用於不相交集合的數據結構，看來某個時候卻有妙用啊。。。

   代碼如下：
#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;
}