并查集2

并查集路径压缩优化方法讲解并查集（Disjoint Set Union）是一种用于解决连通性问题的数据结构，常用于判断图中两个节点是否属于同一个连通分量。

在并查集中，每个节点表示一个元素，通过合并节点来构建集合，实现快速的查找和合并操作。

1. 并查集基本原理并查集最初的实现方法是通过使用树来表示集合，其中每个节点通过指向父节点来建立树结构。

树的根节点表示集合的代表元素，每个节点的父节点指向它所属集合的代表元素。

2. 查找操作查找操作用于找到某个元素所属的集合，即找到该元素的代表元素。

从给定的元素开始，不断向上查找直到找到根节点，即代表元素。

代码示例：```int find(int[] parent, int x) {if (parent[x] == x) {return x;}parent[x] = find(parent, parent[x]); // 路径压缩return parent[x];}```这段代码中的`find`方法使用了递归来实现路径压缩。

路径压缩的核心思想是将查找路径上的每个节点直接指向根节点，从而减少后续的查找时间。

3. 合并操作合并操作用于将两个集合合并成一个，即将两个集合的根节点连接起来。

合并操作可以简单地将一个根节点的父节点指向另一个根节点，从而实现合并。

代码示例：```void union(int[] parent, int x, int y) {int rootX = find(parent, x);int rootY = find(parent, y);if (rootX != rootY) {parent[rootX] = rootY;}}```4. 路径压缩优化路径压缩优化通过将每个节点直接指向根节点，使得查找操作的路径更短。

在常规的实现中，每个节点的父节点都指向其根节点，但这会导致树的高度较高，进而影响查找操作的性能。

路径压缩优化在查找操作中，将经过的节点直接指向根节点，从而使得树的高度减少。

并查集的路径压缩并查集（Disjoint Set）是一种用于解决“动态连通性”问题的数据结构。

它主要用于维护一个不相交的集合，支持快速判断两个元素是否属于同一个集合，以及合并两个集合。

并查集的路径压缩是一种优化算法，用于减少查找操作的时间复杂度。

1. 并查集基本操作并查集包括以下几种基本操作：初始化并查集、查找元素所属的集合、合并两个集合。

1.1 初始化并查集初始化并查集时，每个元素都是一个独立的集合。

可以使用数组来表示并查集，数组索引表示元素，数组值表示元素所属的集合。

示例：```cppint parent[MAX_SIZE];void init(int n) {for (int i = 0; i < n; i++) {parent[i] = i;}}```在上述示例中，`MAX_SIZE`表示并查集的最大容量，`init`函数用于初始化并查集。

1.2 查找元素所属的集合查找元素所属的集合时，可以通过递归的方式查找祖先节点，直到找到根节点。

示例：```cppint find(int x) {return parent[x] == x ? x : find(parent[x]);}```在上述示例中，`find`函数用于查找元素所属的集合，递归调用`find`函数可以找到根节点。

1.3 合并两个集合合并两个集合时，可以通过将一个根节点的父节点指向另一个根节点，将两个集合合并为一个集合。

示例：```cppvoid merge(int x, int y) {int root_x = find(x);int root_y = find(y);if (root_x != root_y) {parent[root_x] = root_y;}}```在上述示例中，`merge`函数用于合并两个集合，首先找到两个集合的根节点，然后将一个根节点的父节点指向另一个根节点。

2. 并查集路径压缩并查集的路径压缩是一种优化算法，通过将节点在查找的过程中直接指向根节点，减少后续查找的时间复杂度。

并查集的空间复杂度并查集是一种常用的数据结构，用于解决集合合并和查找问题。

它可以高效地判断两个元素是否属于同一个集合，以及将两个集合合并为一个集合。

在实际应用中，我们经常需要考虑并查集的空间复杂度，即所需的内存空间大小。

并查集的空间复杂度主要由两个方面决定：底层数据结构和优化策略。

底层数据结构一般是一个数组，其中每个元素表示一个节点，初始化时每个节点都是一个独立的集合。

优化策略包括按秩合并和路径压缩。

在一般情况下，我们假设并查集中有 n 个元素需要处理，那么底层数组的大小就是 n。

这就是并查集的最基本实现方式，它的空间复杂度为 O(n)。

由于只需要一个数组，所以其他数据结构的额外空间消耗不大。

当然，我们可以根据具体的应用场景和需求来进行优化，以减少并查集的空间复杂度。

接下来，我将介绍几种常见的优化策略。

1. 按秩合并：按秩合并是指将高度较小的树合并到高度较大的树上，从而尽量避免树的高度过高。

这样可以减少查找和合并操作的时间复杂度，并且可以降低内存的使用。

2. 路径压缩：路径压缩是指在查找操作时，将节点直接连接到根节点，以减少后续查找操作的时间复杂度。

这种优化策略可以使得树的高度非常小，进一步提高了并查集的性能和空间效率。

这两种优化策略可以独立使用，也可以同时使用。

按秩合并和路径压缩都可以通过修改底层数组来实现，而不需要额外的存储空间。

此外，还可以通过分组合并和启发式合并等策略来进行空间优化。

分组合并是指将元素分组，每个组使用一个并查集来处理，从而降低了整个并查集的空间复杂度。

启发式合并是指根据实际需求，选择合适的合并策略，以减少内存的使用。

综上所述，并查集的空间复杂度与底层数据结构和优化策略密切相关。

一般来说，最基本的实现方式空间复杂度为 O(n)。

而通过一些优化策略，如按秩合并和路径压缩等，可以减少内存的使用，提高并查集的性能。

在应用并查集解决问题时，我们需要综合考虑空间复杂度和时间复杂度，选择适合的优化策略和数据结构。

并查集的两种实现（按秩合并+路径压缩）并查集：就是有求并集，查找元素属于哪个集合的功能。

1、路径压缩：使X到根上的每⼀个节点的⽗节点都变为根节点。

查询：void Find(int x){if(a[x]==0) return x;else return a[x]=Find(a[x]);}合并：void Merge(int x,int y){int t1=Find(x),t2=Find(y);if(t1!=t2) a[t1]=t2;}2、按秩合并：使较浅的树成为较深的树的⼦树。

查询：void Find(int x){if(a[x]==0) return x;else return a[x]=Find(a[x]);}合并：void Merge(int x,int y){int t1=Find(x),t2=Find(y);if(t1!=t2){if(rank[t1]<=rank[t2]) a[t1]=t2,rank[t2]=max(rank[t2],rank[t1]+1);else a[t2]=t1,rank[t1]=max(rank[t1],rank[t2]+1);}}例题：解法⼀：路径压缩#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 1200;int fa[maxn];int f(int x){if(fa[x]==0) return x;else return fa[x]=f(fa[x]);}int main(void){int n,m,t1,t2,i,x,y;while(~scanf("%d",&n)&&n){scanf("%d",&m);memset(fa,0,sizeof(fa));while(m--){scanf("%d%d",&x,&y);t1=f(x),t2=f(y);if(t1!=t2) fa[t1]=t2;}int cnt=0;for(i=1;i<=n;i++){if(fa[i]==0) cnt++;}printf("%d\n",cnt-1);}return0;}View Code解法⼆：按秩求和#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 1200;int fa[maxn],rk[maxn];int f(int x){if(fa[x]==0) return x;else return fa[x]=f(fa[x]);}int MAX(int x,int y){return x>y?x:y;}int main(void){int n,m,x,y,t1,t2,i;while(~scanf("%d",&n)&&n){scanf("%d",&m);memset(fa,0,sizeof(fa));memset(rk,0,sizeof(rk));while(m--){scanf("%d%d",&x,&y);t1=f(x),t2=f(y);if(t1!=t2){if(rk[t1]<=rk[t2]) fa[t1]=t2,rk[t1]=MAX(rk[t1],rk[t2]+1);else fa[t2]=t1,rk[t2]=MAX(rk[t2],rk[t1]+1);}}int cnt=0;for(i=1;i<=n;i++)if(fa[i]==0) cnt++;printf("%d\n",cnt-1);}return0;}View Code。

并查集的应用探讨并查集在实际问题中的应用场景并查集的应用探讨：并查集在实际问题中的应用场景一、引言并查集（Disjoint Set）是一种常用的数据结构，主要用于解决集合的合并与查询问题。

它在实际问题中有着广泛的应用，本文将探讨并查集在实际问题中的应用场景。

二、并查集简介并查集是一种用于处理集合的数据结构，它支持三种操作：查找（Find）、合并（Union）和创建（MakeSet）。

其中查找用于找到元素所属的集合，合并用于将两个集合合并为一个集合，创建则用于创建一个新的集合。

三、应用场景一：网络连通性问题在计算机网络中，经常需要判断两个主机是否能够互相通信或者是否处于同一个网络中。

通过使用并查集来处理网络连通性问题，可以快速判断两个主机是否连通，从而进行相应的网络配置。

以一个局域网中多个主机的连通性判断为例，将每个主机看作一个节点，使用并查集来管理它们的连通关系。

当两个主机通过网络连接后，可以通过合并这两个主机所在的集合，即执行Union操作，将它们放在同一个连通分量中。

当需要判断两个主机是否连通时，只需要执行Find操作判断它们是否属于同一个连通分量即可。

四、应用场景二：社交网络中的朋友圈在社交网络中，人们经常需要查找自己与他人的关系是否存在连接，如朋友圈等。

通过利用并查集，可以快速构建和查询人际关系，判断两个人是否属于同一个朋友圈。

将每个人看作一个节点，使用并查集来管理它们的社交关系。

当两个人成为朋友时，即执行Union操作，将它们放在同一个朋友圈中。

当需要判断两个人是否属于同一个朋友圈时，只需要执行Find操作，判断它们是否属于同一个连通分量即可。

五、应用场景三：图的连通分量在图论中，连通分量是指无向图中的一组顶点，其中任意两个顶点之间都存在路径。

通过并查集，可以快速找到图中的连通分量，从而进行相应的图分析和处理。

以社交网络中用户之间的关注关系为例，将每个用户看作一个节点，使用并查集来管理它们的关系。

洛谷并查集例题洛谷并查集例题是一个经典的数据结构问题，它涉及到如何使用并查集来处理一些集合合并与查询的问题。

以下是一个可能的洛谷并查集例题的样例：题目描述：给定一个整数N，表示有N个元素。

接下来有M个操作，每个操作有3个整数X、Y和Z，表示将X和Y所在的集合合并，并输出是否成功。

如果Z=1，则合并X和Y所在的集合；如果Z=2，则判断X和Y是否在同一个集合中。

样例输入：4 71 2 11 3 22 4 12 3 32 1 4样例输出：NYNY解题思路：洛谷并查集例题的关键在于利用并查集来处理元素的合并与查询。

在解题过程中，我们需要维护一个并查集数据结构，用于记录每个元素所在的集合。

根据题目的要求，我们依次处理每个操作。

如果Z=1，则将X和Y所在的集合合并；如果Z=2，则判断X和Y是否在同一个集合中。

合并集合时，我们找到X和Y所在的根节点，然后将它们连接到同一个集合中；判断是否在同一个集合时，我们直接判断X和Y是否指向同一个根节点即可。

在实现并查集时，我们可以使用数组来存储每个元素的父节点。

对于每个元素，我们可以通过其父节点找到其所在的集合。

为了方便查询，我们还需要维护一个数组来记录每个元素的根节点。

在合并集合时，我们只需要将两个元素的根节点连接到同一个父节点即可。

在查询时，我们只需要判断两个元素的根节点是否相同即可。

总结：洛谷并查集例题是一个经典的数据结构问题，它涉及到如何使用并查集来处理一些集合合并与查询的问题。

解题的关键在于利用并查集来维护元素的集合关系，并根据题目要求进行相应的操作。

在实现并查集时，我们可以使用数组来存储每个元素的父节点和根节点，以便进行快速查询和合并操作。

并查集与的连通性问题并查集与图的连通性问题在图论中，连通性问题是一个非常重要的概念。

它研究的是在一个图中，任意两个节点是否存在路径相连。

而解决这类问题的一种常用数据结构就是并查集。

一、并查集的基本概念并查集（Disjoint Set Union）是一种树型的数据结构，常用于处理不相交集合的合并与查询问题。

它可以高效地判断两个元素是否处于同一集合，并进行集合的合并操作。

在并查集中，每个节点都有一个指针指向它的父节点，如果一个节点的父节点为自己，则代表该节点是集合的代表元素。

为了提高效率，还可以使用路径压缩和按秩合并两种优化策略。

二、并查集的操作1. 初始化操作首先，我们需要将每个元素初始化为一个单独的集合，也就是每个元素的父节点都指向自己。

2. 查找操作查找操作用于判断两个元素是否属于同一个集合。

它通过一层一层地往上查找，直到找到根节点，根节点就是集合的代表元素。

3. 合并操作合并操作用于将两个集合合并为一个集合。

首先需要找到两个元素所在集合的代表元素，然后将其中一个代表元素的父节点指向另一个代表元素。

三、并查集解决连通性问题在图的连通性问题中，可以使用并查集来快速判断两个节点是否连通。

具体步骤如下：1. 初始化并查集，将每个节点都初始化为一个独立的集合。

2. 遍历图中的所有边，对于每条边 (u,v)，找到 u 和 v 所在集合的代表元素。

3. 如果 u 和 v 的代表元素相同，则说明 u 和 v 已经连通，否则将 u 和 v 所在的集合合并。

4. 重复步骤2和步骤3，直到遍历完所有的边。

通过以上操作，就可以得到一个具有连通性信息的图。

在实际应用中，我们可以使用并查集来判断网络中是否存在通路、判断图中是否存在回路等。

四、应用场景举例并查集在算法和数据结构中有广泛的应用场景，例如：1. 最小生成树：使用 Kruskal 算法或者 Prim 算法来构造最小生成树时，可以使用并查集来判断各个节点之间是否连通。

3.3.2 等价类与并查集并查集主要用来解决判断两个元素是否同属一个集合，以及把两个集合合并成一个集合的问题。

“同属一个集合”关系是一个等价关系，因为它满足等价关系（equivalent relation）的三个条件（或称为性质）：1) 自反性：如Ｘ≡Ｘ，则Ｘ≡Ｘ；（假设用“Ｘ≡Ｙ”表示“Ｘ与Ｙ等价”）2) 对称性：如Ｘ≡Ｙ，则Ｙ≡Ｘ；3) 传递性：如Ｘ≡Ｙ，且Ｙ≡Ｚ，则Ｘ≡Ｚ。

如果Ｘ≡Ｙ，则称Ｘ与Ｙ是一个等价对（equivalence）。

等价类（equivalent class）：设R是集合A上的等价关系，对任何a∈A，集合[a]R = { x | x∈A，且a R x }称为元素a形成的R等价类，其中，a R x表示a与x等价。

所谓元素a的等价类，通俗地讲，就是所有跟a等价的元素构成的集合。

等价类应用：设初始时有一集合S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }；依次读若干事先定义的等价对1≡5，4≡2，7≡11，9≡10，8≡5，7≡9，4≡6，3≡12，12≡1；现在需要根据这些等价对将集合S划分成若干个等价类。

在每次读入一个等价对后，把等价类合并起来。

初始时，各个元素自成一个等价类（用{ }表示一个等价类）。

在每读入一个等价对后，各等价类的变化依次为：初始：{ 1 }, { 2 }, { 3 }, { 4 }, { 5 }, { 6 }, { 7 }, { 8 }, { 9 }, { 10 }, { 11 }, { 12 }1≡5：{ 1, 5 }, { 2 }, { 3 }, { 5 }, { 6 }, { 7 }, { 8 }, { 9 }, { 10 }, { 11 }, { 12 }4≡2：{ 1, 5 }, { 2, 4 }, { 3 }, { 6 }, { 7 }, { 8 }, { 9 }, { 10 }, { 11 }, { 12 }7≡11：{ 1, 5 }, { 2, 4 }, { 3 }, { 6 }, { 7, 11 }, { 8 }, { 9 }, { 10 }, { 12 }9≡10：{ 1, 5 }, { 2, 4 }, { 3 }, { 6 }, { 7, 11 }, { 8 }, { 9, 10 }, { 12 }8≡5：{ 1, 5, 8 }, { 2, 4 }, { 3 }, { 6 }, { 7, 11 }, { 9, 10 }, { 12 }7≡9：{ 1, 5, 8 }, { 2, 4 }, { 3 }, { 6 }, { 7, 9, 10, 11 }, { 12 }4≡6：{ 1, 5, 8 }, { 2, 4, 6 }, { 3 }, { 7, 9, 10, 11 }, { 12 }3≡12：{ 1, 5, 8 }, { 2, 4, 6 }, { 3, 12 }, { 7, 9, 10, 11 }12≡1：{ 1, 3, 5, 8, 12 }, { 2, 4, 6 }, { 7, 9, 10, 11 }并查集（union-find set）这个数据结构可以方便快速地实现这个问题。

并查集应用场景全面梳理在计算机科学领域中，并查集是一种常用的数据结构，用于解决一些集合相关的问题。

并查集主要用于维护一组不相交的动态集合，并支持合并两个集合以及查询两个元素是否属于同一集合的操作。

本文将全面梳理并查集的应用场景，并介绍它们在不同领域的实际应用。

一、社交网络中的好友圈关系建立与查询在社交网络中，人与人之间存在着好友关系。

通过并查集可以方便地建立和查询好友圈关系。

首先，我们可以将每个人看作一个节点，利用并查集建立这些节点之间的关系。

当两个人成为好友时，我们将它们所在的两个集合进行合并操作。

通过查询某两个人是否属于同一个集合，我们就可以判断他们是否在同一个好友圈中。

二、电子地图中的连接性问题解决在电子地图中，我们经常需要判断两个地点之间是否存在路径。

并查集可以用来解决这个连接性问题。

我们可以将地图上的每个地点看作一个节点，利用并查集来表示各个地点的连接关系。

当两个地点之间存在路径时，我们将它们所在的两个集合进行合并操作。

通过查询两个地点是否属于同一个集合，我们就可以判断它们之间是否存在路径。

三、图像分割与图像压缩在图像处理领域，图像分割和图像压缩是非常重要的应用。

并查集可以用来实现图像分割的算法。

我们可以将图像的像素看作节点，利用并查集来表示各个像素的连通性。

通过对图像像素进行合并操作，将相邻像素划分为同一个集合，从而实现图像分割。

此外，图像压缩也可以借助并查集来实现。

通过将相邻像素合并为同一集合，减少图像中的冗余信息，从而实现图像压缩。

四、互联网网络中的网络连接问题在互联网网络中，我们经常需要处理网络连接的问题。

并查集可以被应用于解决网络连接问题。

我们可以将网络中的每个节点看作一个机器或者设备，利用并查集来表示网络中各个节点的连接关系。

通过对两个节点进行合并操作，将它们所在的集合合并为一个集合，从而建立网络连接。

通过查询两个节点是否属于同一个集合，我们就可以判断它们之间是否存在网络连接。

信息学奥赛中的特殊数据结构——并查集在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。

一、数学准备首先，我们从数学的角度给出等价关系和等价类的定义：定义1：如果集合S中的关系R是自反的，对称的，传递的，则称他为一个等价关系。

——自反：x＝x；——对称：若x＝y，则y＝x；——传递：若x＝y、y＝z，则x＝z。

要求：x、y、z必须要同一个子集中。

定义2：如果R是集合S的等价关系。

对于任何x∈S，由[x]R＝{y|y∈S and xRy}给出的集合[x]R S称为由x∈S生成的一个R的等价类。

定义3：若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。

即可以按R将S划分为若干不相交的子集S1，S2，S3，S4，……，他们的并即为S，则这些子集S i变称为S的R等价类。

划分等价类的问题的提法是：要求对S作出符合某些等价性条件的等价类的划分，已知集合S及一系列的形如“x等价于y”的具体条件，要求给出S的等价类的划分，符合所列等价性的条件。

（我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合S划分成n个联系的子集，然后再判断x，y是否在一个联系子集中。

）二、引题——亲戚（relation）【问题描述】若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。

java——并查集UnionFind 时间复杂度： O(log*n)，近乎是O(1)级别的UnionFind 接⼝：public interface UF {int getSize();boolean isConnected(int p, int q);void unionElements(int p, int q);}第⼀种：//quickFindpublic class UnionFind1 implements UF{//id 这个数组中并没有存储数据的值，⽽是存储了数据所在的集合编号private int[] id;public UnionFind1(int size) {id = new int[size];for(int i = 0 ; i < id.length ; i ++) {id[i] = i;}}@Overridepublic int getSize() {return id.length;}//查找元素p所对应的集合编号private int find(int p) {if(p < 0 || p >= id.length) {throw new IllegalArgumentException("p is out of bound.");}return id[p];}//查看元素p和q是否属于同⼀个集合@Overridepublic boolean isConnected(int p, int q) {// TODO Auto-generated method stubreturn find(p) == find(q);}//将p和q所属的集合合并@Overridepublic void unionElements(int p, int q) {// TODO Auto-generated method stubint pID = find(p);int qID = find(q);if(pID == qID) {return;}for(int i = 0 ; i < id.length ; i ++) {if(id[i] == pID) {id[i] = qID;}}}}第⼆种：//QuickUnion//⼀种孩⼦指向⽗亲节的树public class UnionFind2 implements UF{private int[] parent;public UnionFind2(int size) {parent = new int[size];//初始的时候每⼀个节点都指向他⾃⼰，每⼀个节点都是⼀棵独⽴的树for(int i = 0 ; i< size ; i ++) {parent[i] = i;}}@Overridepublic int getSize() {return parent.length;private int find(int p) {if(p < 0 || p >= parent.length) {throw new IllegalArgumentException("p is out of bound."); }while(p != parent[p]) {p = parent[p];}return p;}@Overridepublic boolean isConnected(int p, int q) {return find(p) == find(q);}@Overridepublic void unionElements(int p, int q) {int pRoot = find(p);int qRoot = find(q);if(pRoot == qRoot) {return;}else {parent[pRoot] = qRoot;}}}第三种：package UnionFind;//使树的深度尽量保持较低⽔平//节点总数⼩的那个树去指向节点总数⼤的那棵树public class UnionFind3 implements UF {private int[] parent;// sz[i]表⽰以i为根的的集合中元素的个数private int[] sz;public UnionFind3(int size) {parent = new int[size];for(int i = 0 ; i < parent.length ; i ++) {parent[i] = i;sz[i] = 1;}}@Overridepublic int getSize() {// TODO Auto-generated method stubreturn parent.length;}private int find(int p) {if(p < 0 || p >= parent.length) {throw new IllegalArgumentException("p is out of bound."); }while(p != parent[p]) {p = parent[p];}return p;}@Overridepublic boolean isConnected(int p, int q) {return find(p) == find(q);}@Overridepublic void unionElements(int p, int q) {int pRoot = find(p);int qRoot = find(q);if(pRoot == qRoot) {return;}if(sz[pRoot] < sz[qRoot]) {parent[pRoot] = qRoot;sz[qRoot] += sz[pRoot];}else {parent[qRoot] = pRoot;sz[pRoot] += sz[qRoot];}}}第四种：//基于rank的优化//使深度⼩的那棵树指向深度⼤的那棵树public class UnionFind4 implements UF {private int[] parent;// rank[i]表⽰以i为根的的集合所表⽰的树的层数private int[] rank;public UnionFind4(int size) {parent = new int[size];for(int i = 0 ; i < parent.length ; i ++) {parent[i] = i;rank[i] = 1;}}@Overridepublic int getSize() {// TODO Auto-generated method stubreturn parent.length;}private int find(int p) {if(p < 0 || p >= parent.length) {throw new IllegalArgumentException("p is out of bound."); }while(p != parent[p]) {p = parent[p];}return p;}@Overridepublic boolean isConnected(int p, int q) {return find(p) == find(q);}@Overridepublic void unionElements(int p, int q) {int pRoot = find(p);int qRoot = find(q);if(pRoot == qRoot) {return;}if(rank[pRoot] < rank[qRoot]) {parent[pRoot] = qRoot;}else if(rank[pRoot] > rank[qRoot]){parent[qRoot] = pRoot;}else {parent[qRoot] = pRoot;rank[pRoot] += 1;}}}第五种：//路径压缩public class UnionFind5 implements UF{private int[] parent;// rank[i]表⽰以i为根的的集合所表⽰的树的层数private int[] rank;public UnionFind5(int size) {parent = new int[size];for(int i = 0 ; i < parent.length ; i ++) {parent[i] = i;rank[i] = 1;}}@Overridepublic int getSize() {// TODO Auto-generated method stubreturn parent.length;}//这⾥添加路径压缩的过程private int find(int p) {if(p < 0 || p >= parent.length) {throw new IllegalArgumentException("p is out of bound.");while(p != parent[p]) {parent[p] = parent[parent[p]];p = parent[p];}return p;}@Overridepublic boolean isConnected(int p, int q) {return find(p) == find(q);}//这⾥的rank不再是每个节点精准的深度，只是做为⼀个参考，由于性能考虑所以不维护rank @Overridepublic void unionElements(int p, int q) {int pRoot = find(p);int qRoot = find(q);if(pRoot == qRoot) {return;}if(rank[pRoot] < rank[qRoot]) {parent[pRoot] = qRoot;}else if(rank[pRoot] > rank[qRoot]){parent[qRoot] = pRoot;}else {parent[qRoot] = pRoot;rank[pRoot] += 1;}}}第六种：//find过程中让每个节点都指向根节点//路径压缩public class UnionFind6 implements UF{private int[] parent;// rank[i]表⽰以i为根的的集合所表⽰的树的层数private int[] rank;public UnionFind6(int size) {parent = new int[size];for(int i = 0 ; i < parent.length ; i ++) {parent[i] = i;rank[i] = 1;}}@Overridepublic int getSize() {// TODO Auto-generated method stubreturn parent.length;}//这⾥添加路径压缩的过程//递归调⽤private int find(int p) {if(p < 0 || p >= parent.length) {throw new IllegalArgumentException("p is out of bound.");}if(p != parent[p]) {parent[p] = find(parent[p]);}return parent[p];}@Overridepublic boolean isConnected(int p, int q) {return find(p) == find(q);}//这⾥的rank不再是每个节点精准的深度，只是做为⼀个参考，由于性能考虑所以不维护rank @Overridepublic void unionElements(int p, int q) {int pRoot = find(p);int qRoot = find(q);if(pRoot == qRoot) {return;}if(rank[pRoot] < rank[qRoot]) {parent[pRoot] = qRoot;}else if(rank[pRoot] > rank[qRoot]){parent[qRoot] = pRoot;}else {parent[qRoot] = pRoot; rank[pRoot] += 1;}}}。

并查集的初级应用及进阶一、精华精华提炼1：内容：并查集就是树的孩子表示法的应用。

解释：对于下图所示树，它的孩子表示法为：belg[5]=2, belg[6]=2, belg[7]=2;belg[2]=1, belg[3]=1, belg[4]=1;belg[1]=1(也可以=-1,只要能够识别它是根就可以)精华提炼2：内容：并查集的孩子父亲表示法中，每个节点与其父亲节点可以添加一个关系属性(必须具有可传递性)。

解释：比如，节点表示一个人，关系属性为一个人的性别。

我们先用上图来解释这个关系属性的应用，在后文具体展开。

我们可以这样定义，如果节点i和其父节点j性别相同（belg[i]=j），则kind[i]=false, 反之，kind[i]=true，那么如果我们知道kind[5]=true，kind[2]=false，那么5和2的父节点1的关系为kind[5]^kind[2]=true，即他们性别不同。

二、基础基础1：集合表示根据精华提炼1，我们把一颗树的节点集合看成以根节点命名的集合，那么上面的集合我们可以认为是集合1。

下图共有两个集合，分别为集合1，集合2。

基础2：元素关系如何判断元素关系呢？其实，我们只需找出元素对应的集合名称，然后判断名称是否相同即可。

寻找集合名称代码如下：int Find(int x){while ( belg[x]!=x )x = belg[x];return x;}例如：对于基础1中左图,有belg[5]=2，belg[2]=2。

那么5属于集合2。

现在我们已经解决了元素关系问题。

基础3：集合合并集合如何合并呢？基础2中，我们已经可以找到元素对应集合的名称（即根节点标号），如果元素u、v （u、v不在同一集合）对应的集合名称为_u、_v，那么语句belg[_u]=_v什么意思呢？想到了吧？就是把集合_u与集合_v合并，并且以_v命名。

至此，通过基础部分我们知道了什么是并查集，通过精华提炼部分，我们知道了并查集的高级应用（精华提炼2）。

并查集--学习详解文章作者：yx_th000文章来源：Cherish_yimi (/cherish_yimi/) 转载请注明，谢谢合作。

昨天和今天学习了并查集和trie树，并练习了三道入门题目，理解更为深刻，觉得有必要总结一下，这其中的内容定义之类的是取自网络，操作的说明解释及程序的注释部分为个人理解。

并查集学习：●并查集：(union-find sets)一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数等。

最完美的应用当属：实现Kruskar算法求最小生成树。

●并查集的精髓（即它的三种操作，结合实现代码模板进行理解）：1、Make_Set(x) 把每一个元素初始化为一个集合初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身（也可以根据情况而变）。

2、Find_Set(x) 查找一个元素所在的集合查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！这个才是并查集判断和合并的最终依据。

判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。

合并两个集合，也是使一个集合的祖先成为另一个集合的祖先，具体见示意图3、Union(x,y) 合并x,y所在的两个集合合并两个不相交集合操作很简单：利用Find_Set找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。

如图●并查集的优化1、Find_Set(x)时路径压缩寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find_Set(x)都是O(n)的复杂度，有没有办法减小这个复杂度呢？答案是肯定的，这就是路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Find_Set(x)时复杂度就变成O(1)了，如下图所示；可见，路径压缩方便了以后的查找。