这是并查集最后一题,据说也是最经典的一题。经常前面几题的训练,这题的思路很快就能想出来了.只需要对每个节点附加一个信息表示离根节点的距离,并且距离是模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; }
|