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