带你了解并查集

什么是并查集

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

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

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

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

问题1：

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

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

问题二：

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

 

这个问题也很容易了，根据关系集合进行合如果两个元素已经属于一个集合，那就说明不满足要求啦。

并查集解析

通过上面介绍，相信你已经清楚并查集就是解决集合中一些元素的合并和查询问题，现在就带你解析这个算法。

初始化

开始时候森林中每个元素没有任何操作，它们之间是相互独立的。我们通常会使用数组来表示这个森林(数组下标对应第几个元素)，在初始化的时候数组中的各个值为-1，表示各自自己是一个集合(各自为王)，你可能会问为啥是-1而不是一个其他的数，那是因为用负数可以代表这个元素是某个集合的根，然后它的权值表示集合中元素的个数。

 

并 union(int a,int b)

这里合并，并没有你想象的直接合并那么简单，这里合并是合并a所在的集合和b所在的集合，但在操作层面a,b可能并不是根节点，所以也要先判断一下。

为了便于理解，这里罗列一下最初操作可能的情况，初始时候各个元素都是独立的集合，那么直接a指向b(或者b指向a)即arr[a]=b,同时为了表示这个集合有多少个，原本-1的b再次-1.即arr[b]=-2.表示以b为父根的集合节点有|-2|个。例如进行union(1,4)，union(5,7)操作之后