什么是并查集

并查集这种数据结构，可能出现的频率不是那么高，但是还会经常性的见到，其理解学习起来非常容易，通过本文，一定能够轻轻松松搞定并查集!

对于一种数据结构，肯定是有自己的应用场景和特性，那么并查集是处理什么问题的呢?

并查集是一种树型的数据结构，用于处理一些不相交集合(disjoint sets)的合并及查询问题,常常在使用中以森林来表示。在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受;即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间(1～3秒)内计算出试题需要的结果，只能用并查集来描述。

你可能还有点迷糊并查集能怎么玩，看完这篇然后回头看这两个问题(分别杭电1232和杭电1272)。

问题1：

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?

这个问题很容易，给定的关系看看需要合并多少次就知道最少的建设道路数量。

问题二：

小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。

（编辑：漯河站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!