并查集算是，巧妙的不行，让人为之一惊。

在学习数据结构Q的时候，老师多少会提到并查集，他的应用也是超级广泛。本文首先会通过案例来对并查集有一个介绍。然后给出并查集的java实现。

刚好我有一些资料，是我根据网友给的问题精心整理了一份「数据结构的资料从专业入门到高级教程」，

点个关注在评论区回复“888”之后私信回复“888”，全部无偿共享给大家！！！

一、并查集原理

话说在江湖上有很多门派，这些门派相互争夺武林霸主。毕竟是江湖中人，两个人见面一言不合就开干。但是打归打，总是要判断一下是不是自己人，免得误伤。于是乎，分了各种各样的门派，比如说张无忌和杨过俩人要打架，就先看看是不是同一门派的，不是的话那就再开干。要是张无忌和杨过觉得俩人合得来，那就合并门派。

而且规定了，每一个门派都有一个掌门人，比如武当派R就是张三丰。华山派就是岳不群等等。现在我们把目光转到并查集上。

(1）张无忌和杨过打架之前，先判断是否是同一门派，这就涉及到了并查集的查找操作。(2）张无忌和杨过觉得俩人合得来，那就合并门派，这就涉及到了并查集的合并操作。

(3)每一个门派都有一个掌门人，这涉及到了并查集的存储方式。掌门人代表了这个门派的根节点。

现在我们从这个例子的思想开始认识一下并查集口。二、并查集简单实现

并查集主要涉及到两种操作，合并和查找。假设有一个动态集合Q:S=(s1，s2，s3，.….n}。在这个集合里面每一个元素都是一个江湖人物。比如S1代表了岳不群等等。

我们实现一个并查集的时候首先要考虑的就是存储结构，一般情况下有两种:数组和链表。现在我们使用数组来实现一下。