┎结构之美┒之并查集
顾名思义，并查集的功能是并和查，但并和查的对象是什么呢？针对的是集合。所以我想了一个例子给大家讲解，咱不说概念性晦涩的东西。通俗易懂，直接来看图：
这是我做的一张两个IT公司的公司人员结构，当然两个公司就不用介绍了，现在问题来了：比如我想知道Steve Ballmer和worker4是不是一个公司的该怎么办？我们可以定义一个结构体，里面有个属性叫company来记录一个人的公司，这样就浪费大量的空间；还可以定义一个传统的树形结构来存储每个节点，然后搜索根节点，找到大Boss，然后比较两个Boss如果是同一个人他们就在一个公司，但多次判断两个人在不在同一个公司，或者多次判断某个人在不在某个公司显然又浪费了大量的时间。这时就该我们的并查集登场了，我们假设先把这些人编上号，如下图：
假如我们知道所有的两人的上下级关系，然后我们申请一个set[10]的数组（大于7就可以）我们把所有人存在这个数组里，我们就利用这个set数组记录存在上下级关系的两个人，比如set的下标4就代表worker2(编号为4的人)，而set[4]的值代表worker2(编号为4)的上司steve ballmer(编号为2)，我们的思想就是找到两个员工顶级Boss，如果Boss是一个人当然就在同一个公司，如果不是一个人，则不在一个公司。比如判断2和7在不在同一个公司，显然set[4] = 2.set[2] = 1, 1是Mirosoft的Boss；set[7] = 5, 5是Skype的Boss，显然很容易判断他们不在公司（包含判断4在不在Mirosoft的问题）。这便是并查集“查”的功能。
下面我们来看“并”是什么意思。大家都知道Mirosoft在2011年5月收购了Skype。但是过程是怎么样的呢？我来给大家讲个小故事（以下故事存属虚构）：话说一天worker3找到worker4说想让Mirosoft收购Skype。但他们做不了主，于是他们分别知道了他们的直接上司，worker3找到了Tony Bates，他是大Boss有权力答应这事而且也同意了，但是worker2的上司是Steve Ballmer他没权利，于是他把这事告诉了他的直接上司Bill Gates。于是Bill Gates和Tony Bates一拍桌子，行！于是Tony Bates当了Bill Gates的直接下属，如下图：
但是收购成功之前，由于Worker2的收购想法，Bill Gates决定给Worker2及Worker2的上司，和上司的上司...一直到Bill Gates的二级下属升职，由Bill Gates直接管理，因为Steve Ballmer已经是Bill Gates的直接下属了，职位不用变，所以就演变成了下图：
这其实就是并查集的“路径压缩”，在每次搜索到Boss的时候，把路径上所有的节点都直接接到Boss的下面，这样以后再搜索Worker2就省时间啦。
看到这里相信大家已经对并查集有所了解，下面我就用程序模拟上述过程。
先配个数字的转换图方便大家对照：
代码清单：
总之：并查集是判断或维护图的连通性的数据结构。
==================================================================================================
作者：nash_ 欢迎转载，与人分享是进步的源泉！
转载请保留原文地址：http://blog.csdn.net/nash_/article/details/8252925
===================================================================================================
