AcWing 836. 并查集(数组)
先说一下本题思路
-
1.看清题目,主要有俩个操作,合并和查询 。 总体思路是找到俩个祖宗节点,并且把俩个祖宗节点相连(其实就是改p[a的祖宗]=b的祖宗 比如p[3]=4,p[3]=p[4]=4,他们的祖宗都是4,)
-
2.合并是在一个数组中,利用下标和他所指向的值,如果他所指向的值一样,那么就是一个集合。用下表来记录具体数据。
-
3.查询直接查询祖宗节点,很好理解,就是比如说查询x,他就会查询p[x]的值,如果和x不一样,会查询find[p[x]]的值,这里有点绕,x如果和p[x]的值不一样,就查询find(p[x]),一个个找,找到祖宗节点,就是x和p[x]一样的节点,原始节点。
-
主要操作就是针对于祖宗节点进行的。
-
题目难点(个人愚见):find函数,寻找祖宗节点的过程,下标和值的用法。
1 | #include <iostream> |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 impdx!