并查集應(yīng)用的變形。
給出的是2個(gè)節(jié)點(diǎn)是敵對(duì)關(guān)系的信息，最后詢問任意2個(gè)節(jié)點(diǎn)的關(guān)系。根據(jù)這些信息，
節(jié)點(diǎn)之間可能是敵對(duì)的，也可能不是的（因?yàn)閿橙说臄橙司褪桥笥眩部赡芙o出的
信息根本描述不了它們的關(guān)系。
看起來跟原始的并查集應(yīng)用差遠(yuǎn)了。。。
有個(gè)比較直接的做法，那么就是把不在一個(gè)集合的節(jié)點(diǎn)直接用并查集合并在一起。這樣的話，
如果詢問的2個(gè)節(jié)點(diǎn)在同一個(gè)并查集里面，那么它們之間的關(guān)系是確定的，否則無法確定它們的
關(guān)系。
現(xiàn)在還有一個(gè)問題是，在同一個(gè)并查集里面的2個(gè)節(jié)點(diǎn)是敵對(duì)關(guān)系還是朋友關(guān)系。。。
可以給每個(gè)節(jié)點(diǎn)另外附加個(gè)信息，記錄其距離并查集根節(jié)點(diǎn)的距離。如果，詢問的2個(gè)節(jié)點(diǎn)距離
其根節(jié)點(diǎn)的距離都是奇數(shù)或者都是偶數(shù)，那么這2個(gè)節(jié)點(diǎn)是朋友關(guān)系，否則是敵對(duì)關(guān)系。。。
代碼如下：
#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;
}