poj 1182 食物链 并查集

这是并查集最后一题,据说也是最经典的一题。经常前面几题的训练,这题的思路很快就能想出来了.只需要对每个节点附加一个信息表示离根节点的距离,并且距离是模3循环的。注意合并时候保持距离变化的正确性。而且合并有2种情况,距离相同合并和距离不同合并。分别对应于题目描述中的1和2操作。
关键还是FindSet里面对距离nDis数组里面的修改,前面一直写错这个,wa了好几次,还是看队友代码才一眼发现我又把这里写错了。。。当前距离的更新还是等于当前距离加上前一个节点的距离再模3,类似于前面几题的更新方法。
这种将有关系的节点放在一个并查集里面,再给每个节点附加其它信息描述其它关系的做法,确实比较有效。。。并查集是应用于不相交集合的数据结构,看来某个时候却有妙用啊。。。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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;
}