poj 1703 Find them, Catch them 並查集

 並查集應用的變形。
   給出的是2個節點是敵對關系的信息，最後詢問任意2個節點的關系。根據這些信息，
節點之間可能是敵對的，也可能不是的（因為敵人的敵人就是朋友），也可能給出的
信息根本描述不了它們的關系。
   看起來跟原始的並查集應用差遠了。。。
   有個比較直接的做法，那麼就是把不在一個集合的節點直接用並查集合並在一起。這樣的話，
如果詢問的2個節點在同一個並查集裡面，那麼它們之間的關系是確定的，否則無法確定它們的
關系。
   現在還有一個問題是，在同一個並查集裡面的2個節點是敵對關系還是朋友關系。。。
   可以給每個節點另外附加個信息，記錄其距離並查集根節點的距離。如果，詢問的2個節點距離
其根節點的距離都是奇數或者都是偶數，那麼這2個節點是朋友關系，否則是敵對關系。。。

   代碼如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX_N = 100010;
int nSets[MAX_N];
int nDis[MAX_N];

int nN, nM;

void MakeSets(int nNum)
{
    for (int i = 0; i < nNum; ++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[nI] + nDis[nPre]) % 2;
    }
    return nSets[nI];
}

void UnionSet(int nI, int nJ)
{
    int nA = FindSet(nI);
    int nB = FindSet(nJ);
    if (nA != nB)
    {
        nSets[nA] = nB;
        nDis[nA] = (nDis[nI] + nDis[nJ] + 1) % 2;
    }
}

int main()
{
    int nT;
   
    scanf("%d", &nT);
    while (nT--)
    {
        scanf("%d%d", &nN, &nM);
        MakeSets(nN);
        char szOper[10];
        int nA, nB;
        while (nM--)
        {
            scanf("%s%d%d", szOper, &nA, &nB);
            if (szOper[0] == 'D')
            {
                UnionSet(nA, nB);
            }
            else
            {
                int nX = FindSet(nA);
                int nY = FindSet(nB);
                if (nX == nY)
                {
                    if (nDis[nA] == nDis[nB])
                    {
                        printf("In the same gang.\n");
                    }
                    else
                    {
                        printf("In different gangs.\n");
                    }
                }
                else
                {
                    printf("Not sure yet.\n");
                }
            }
        }
    }
   
    return 0;
}