并查集(高级数据结构)-蓝桥杯

比眉伴天荒 2023-09-24 18:35 110阅读 0赞

# **一、并查集** #

*  **并查集(Disioint Set)：一种非常精巧而实用的数据结构·用于处理不相交集合的合并问题。**

*  **用于处理不相交集合的合并问题。**

*  **经典应用：**

*  **连通子图。**

*  **最小生成树Kruskal算法。**

*  **最近公共祖先。**

# **二、应用场景** #

有n个人，他们属于不同的帮派。
    已知这些人的关系，例如1号、2号是朋友，1号、3号也是朋友，那么他们都属于一个帮派。
    问有多少帮派，每人属于哪个帮派。
    
    有n个人一起吃饭，有些人互相认识认识的人想坐在一起，而不想跟陌生人坐。
    例如A认识B，B认识C，那么A、B、C会坐在一张桌子上。
    给出认识的人，问需要多少张桌子。

![fdd0a6cba3bb4c04a91c23ee07af50b0.png][]

![a6eab24e98664720806bf1add5595c84.png][]

*  **用并查集可以很简洁地表示这个关系。**

# **三、并查集的操作** #

*  ## **初始化** ##

*  **定义s\[ \]是以结点i为元素的并查集。**

*  **初始化：令s\[i\]=i (联想：某人的号码是i，他属于帮派s\[i\])。**

![32a5a1bfbcdb4e999567f9bc6cb5b4bb.png][]

*  ### **代码：** ###

![20ae712d77dd4e58a64bd3f07aad6722.png][]

*  ## **合并** ##

*  **加入第一个朋友关系(1,2)：**

*  **在并查集s中，把结点1合并到结点2，也就是把结点1的集1改成结点2的集2。**

![3d81d6ac32b443298674ba7d332045a2.png][]

*  **加入第二个朋友关系(1,3)：**

*  **查找结点1的集，是2，递归查找元素2的集是2；把元素2的集2合并到结点3的集3。此时，结点1、2、3都属于一个集。**

![fa065292bd1649d1ba0391274b073901.png][]

*  **加入第三个朋友关系(2,4)：**

*  **查找结点1的集，是2，递归查找元素2的集是2；把元素2的集2合并到结点3的集3。此时，结点1、2、3都属于一个集。**

![bd2c29385a614cba9a204111f0e3dfb6.png][]

*  ### **代码：** ###

![cb8f821a956b44e3880128b4bc01ca81.png][]

*  ## **查找** ##

*  **查找元素的集，是一个递归的过程，直到元素的值和它的集相等，就找到了根结点的**

**集。**

*  ### **代码：** ###

![e15db7c2bc594577a128b6584a3af0c0.png][]

*  **这棵搜索树，可能很细长,复杂度O(n)，变成了一个链表，出现了树的“退化”现象。**

*  ## **总结** ##

*  ### **代码：** ###

![c190d0c306284f018f091261b4d8aa17.png][]

# **四、有多少个集(帮派) ?** #

*  **如果s\[i\] = i，这就是一个根结点，是它所在的集的代表(帮主)。统计根结点的数量，就是集的数量。**

*  ## **复杂度：** ##

*  **查找find\_set()、合并merge\_set()的搜索深度是树的长度，复杂度都是O(n)。性能较差，不是高级数据结构应有的复杂度。**

![1861d790bff14431bc6a6b22afe7d619.png][]

*  ## **复杂度的优化：** ##

*  **能优化吗? 能 目标：优化之后，复杂度≈O(1)。**

*  ### **查询的优化(路径压缩)：** ###

*  **查询程序find\_set()：沿着搜索路径找到根结点，这条路径可能很长。**

*  **优化：沿路径返回时，顺便把i所属的集改成根结点。下次再搜，复杂度是O(1)。**

![6e68709e837a42a28f76e4ec1fc456a6.png][]

*  ### **代码：** ###

![c121d200217f4587a473614b64fd6d31.png][]

*  ### **优化前后代码对比：** ###

![c407bf7b61b042cc9aff6b870b3e9c75.png][]

*  ### 路径压缩总结： ###

*  **路径压缩通过递归实现。**

*  **整个搜索路径上的元素，在递归过程中，从元素i到根结点的所有元素，它们所属的集都被改为根结点。**

*  **路径压缩不仅优化了下次查询，而且也优化了合并，因为合并时也用到了查询。**

# **五、蓝桥杯真题(1135号)** #

![0e29d3b8b4b64bf1b34e64c05c52bace.png][]

![3ac666fdbd284943859f19715cab1b59.png][]

--------------------

![c3ae901734884d03a2d702455cfce407.png][]

# **六、**蓝桥杯真题(1135号) #

![e83f9d01f96f4d7e80d0a19a5a31119c.png][]

![df5a8f9f323949d89ddc337b8e7296c9.png][]

![2dcbee9be0984023b9d2f1a875c62db4.png][]

--------------------

![a6ee00bbabef4cc6a79f9d436ec0cb59.png][]

# **七、蓝桥杯真题(185号)** #

![684c6c8af1864ad1973bbd4e5d4ca3ef.png][]

![1144e9a65094449d9fd9bb438a0b5b4e.png][]

--------------------

## **1.暴力法** ##

*  **1≤N≤100000**

*  **每读入一个新的数，就检查前面是否出现过，每一次需要检查前面所有的数。共有n个数，每个数检查O(n)次，总复杂度O(n^3)，超时。**

*  **暴力法1**

![8d733d016612481fbbd35982e3dc4b4d.png][]

*  **暴力法2**

![db1cead6ebe04d08ae7d9120c6f16901.png][]

--------------------

## **2.查重，hash或set()** ##

*  **改进，用hash。定义vis\[\]数组，vis\[i\]表示数字i是否已经出现过。这样就不用检查前面所有的数了，基本上可以在O(1)的时间内定位到。**

*  **或：直接用set判断是否重复，也是O(1)。**

![b29e83ffa64241d6807ef58c6354213b.png][]

--------------------

## **3.改进：记忆法** ##

*  **本题特殊要求：“如果新的Ai仍在之前出现过，小明会持续给Ai加1，直到Ai,没有在A1~Ai-1中出现过。”这导致在某些情况下，仍然需要大量的检查。**

*  **以5个6为例：A\[ \]=\{6,6,6,6,6\}。**

*  **第一次读A\[1\]=6，设置vis\[6\]=1。**

*  **第二次读A\[2\]=6，先查到vis\[6\]=1，则把A\[2\]加1，变为a\[2\]=7；再查vis\[7\]=0，设置vis\[7\]=1。检查了2次。**

*  **第三次读A\[3\]=6，先查到vis\[6\]=1，则把A\[3\]加1得A\[3\]=7； 再查到vis\[7\]=1，再把A\[3\]加1得A\[3\]=8，设置vis\[8\]=1； 最后查vis\[8\]=0，设置vis\[8\]=1。检查了3次。**

......

*  **每次读一个数，仍需检查O(n)次，总复杂度O(n^2)。**

*  **本题用Hash，在特殊情况下仍然需要大量的检查。**

*  **问题出在“持续给Ai加1，直到Ai没有在A1~Ai-1中出现过”。**

*  **也就是说，问题出在那些相同的数字上。当处理一个新的Ai时，需要检查所有与它相同的数字。**

**如果把这些相同的数字看成一个集合，就能用并查集处理。**

*  **用并查集s\[i\]表示访问到i这个数时应该将它换成的数字。**

*  **以A\[ \]=\{6,6,6,6,6\}为例。初始化set\[i\]=i。**

![adf7510ca8814434bebb7052dcbd0771.png][]

*  **图(1)读第一个数A\[0\]= 6。6的集set\[6\]= 6。紧接着更新set\[6\] = set\[7\] = 7，作用是后面再读到某个A\[k\]=6时，可以直接赋值A\[k\] = set\[6\]= 7。**

*  **图(2)读第二个数A\[1\]=6。6的集set\[6\]=7，更新A\[1\]= 7。紧接着更新set\[7\]= set\[8\]= 8。如果后面再读到A\[k\]= 6或7时，可以直接赋值A\[k\]= set\[6\]= 8或者A\[k\]= set\[7\]=8。**

--------------------

*  **只用到并查集的查询，没用到合并。**

*  **必须是“路径压缩”优化的，才能加快查询速度。没有路径压缩的并查集，仍然超时。**

*  **复杂度O(n)**

![14a8b57cac314a1b8fdc137e57f29348.png][]

[fdd0a6cba3bb4c04a91c23ee07af50b0.png]: https://img-blog.csdnimg.cn/img_convert/fdd0a6cba3bb4c04a91c23ee07af50b0.png
[a6eab24e98664720806bf1add5595c84.png]: https://img-blog.csdnimg.cn/img_convert/a6eab24e98664720806bf1add5595c84.png
[32a5a1bfbcdb4e999567f9bc6cb5b4bb.png]: https://img-blog.csdnimg.cn/img_convert/32a5a1bfbcdb4e999567f9bc6cb5b4bb.png
[20ae712d77dd4e58a64bd3f07aad6722.png]: https://img-blog.csdnimg.cn/img_convert/20ae712d77dd4e58a64bd3f07aad6722.png
[3d81d6ac32b443298674ba7d332045a2.png]: https://img-blog.csdnimg.cn/img_convert/3d81d6ac32b443298674ba7d332045a2.png
[fa065292bd1649d1ba0391274b073901.png]: https://img-blog.csdnimg.cn/img_convert/fa065292bd1649d1ba0391274b073901.png
[bd2c29385a614cba9a204111f0e3dfb6.png]: https://img-blog.csdnimg.cn/img_convert/bd2c29385a614cba9a204111f0e3dfb6.png
[cb8f821a956b44e3880128b4bc01ca81.png]: https://img-blog.csdnimg.cn/img_convert/cb8f821a956b44e3880128b4bc01ca81.png
[e15db7c2bc594577a128b6584a3af0c0.png]: https://img-blog.csdnimg.cn/img_convert/e15db7c2bc594577a128b6584a3af0c0.png
[c190d0c306284f018f091261b4d8aa17.png]: https://img-blog.csdnimg.cn/img_convert/c190d0c306284f018f091261b4d8aa17.png
[1861d790bff14431bc6a6b22afe7d619.png]: https://img-blog.csdnimg.cn/img_convert/1861d790bff14431bc6a6b22afe7d619.png
[6e68709e837a42a28f76e4ec1fc456a6.png]: https://img-blog.csdnimg.cn/img_convert/6e68709e837a42a28f76e4ec1fc456a6.png
[c121d200217f4587a473614b64fd6d31.png]: https://img-blog.csdnimg.cn/img_convert/c121d200217f4587a473614b64fd6d31.png
[c407bf7b61b042cc9aff6b870b3e9c75.png]: https://img-blog.csdnimg.cn/img_convert/c407bf7b61b042cc9aff6b870b3e9c75.png
[0e29d3b8b4b64bf1b34e64c05c52bace.png]: https://img-blog.csdnimg.cn/img_convert/0e29d3b8b4b64bf1b34e64c05c52bace.png
[3ac666fdbd284943859f19715cab1b59.png]: https://img-blog.csdnimg.cn/img_convert/3ac666fdbd284943859f19715cab1b59.png
[c3ae901734884d03a2d702455cfce407.png]: https://img-blog.csdnimg.cn/img_convert/c3ae901734884d03a2d702455cfce407.png
[e83f9d01f96f4d7e80d0a19a5a31119c.png]: https://img-blog.csdnimg.cn/img_convert/e83f9d01f96f4d7e80d0a19a5a31119c.png
[df5a8f9f323949d89ddc337b8e7296c9.png]: https://img-blog.csdnimg.cn/img_convert/df5a8f9f323949d89ddc337b8e7296c9.png
[2dcbee9be0984023b9d2f1a875c62db4.png]: https://img-blog.csdnimg.cn/img_convert/2dcbee9be0984023b9d2f1a875c62db4.png
[a6ee00bbabef4cc6a79f9d436ec0cb59.png]: https://img-blog.csdnimg.cn/img_convert/a6ee00bbabef4cc6a79f9d436ec0cb59.png
[684c6c8af1864ad1973bbd4e5d4ca3ef.png]: https://img-blog.csdnimg.cn/img_convert/684c6c8af1864ad1973bbd4e5d4ca3ef.png
[1144e9a65094449d9fd9bb438a0b5b4e.png]: https://img-blog.csdnimg.cn/img_convert/1144e9a65094449d9fd9bb438a0b5b4e.png
[8d733d016612481fbbd35982e3dc4b4d.png]: https://img-blog.csdnimg.cn/img_convert/8d733d016612481fbbd35982e3dc4b4d.png
[db1cead6ebe04d08ae7d9120c6f16901.png]: https://img-blog.csdnimg.cn/img_convert/db1cead6ebe04d08ae7d9120c6f16901.png
[b29e83ffa64241d6807ef58c6354213b.png]: https://img-blog.csdnimg.cn/img_convert/b29e83ffa64241d6807ef58c6354213b.png
[adf7510ca8814434bebb7052dcbd0771.png]: https://img-blog.csdnimg.cn/img_convert/adf7510ca8814434bebb7052dcbd0771.png
[14a8b57cac314a1b8fdc137e57f29348.png]: https://img-blog.csdnimg.cn/img_convert/14a8b57cac314a1b8fdc137e57f29348.png