下载文档原格式
并查集路径压缩优化方法讲解并查集（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 算法来构造最小生成树时，可以使用并查集来判断各个节点之间是否连通。
并查集。
1、概念：
如果：给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。
在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。
并查集是一种树型的数据结构，它是一个集合，这个集合的元素也是集合，常常在使用中以森林来表示。
2、并查集的主要操作：
①合并两个不相交集合
②判断两个元素是否属于同一集合
初步分析觉得本题是一个图论中判断两个点是否在同一个连通子图中的问题。
1、识别水果模9第1题
在海上漂泊了249天后，由于食物和水都已消耗光了，三人已是筋疲力尽。
终于，在第250天的早晨，一个隐隐约约的黑点在远处出现了，是一个小岛，三大护法高兴的几乎要跳起来。
于是下令舰队全速前进，驶向小岛。
在登陆后，他们才知道，这就是著名的移花岛，岛上有三位女神：dp女神、涓涓女神和紫晶女神。
由于三大女神与holy_one的关系不错，因此高兴地接待了他们三人。
由于看到三人饥渴难耐，负责岛上水果的涓涓女神便带他们去了果园。
果园里水果丰富，共有n个，它们的标号为1~n，但有些水果是有毒，而且水果与水果之间有藤蔓相连，如果一个水果有毒，那么所有与它相连的所有水果都是有毒的。
其中m 个水果上面会贴着一个标签，从标签上可以看出这个水果是否有毒。
当然，如果这个水果的标签显示无毒，但它与有毒的水果相连，那它也是有毒的。
为帮助三人尽快吃到水果，涓涓女神给了他们一张毒物字典，只有通过字典上的对应关系翻译后，才能知道水果是否有毒。
转化后的名称中包含'poison'，即表示这个水果有毒。
输入：
第一行，字符串a
第二行，字符串b
a串和b串长度都是26，a[i]到b[i]表示两个字母的对应关系。
注意，对应关系是单向的。
两个整数n和m。
以下m行，
每行第一个数是水果的标号k，后面是第k个水果的标签s
k和s之间有空格分隔开
一个整数p。
以下p行，每行两个整数x,y表示第x个水果和第y个水果之间有藤蔓相连
输出：
无毒的水果的个数s:array[‘a’..’z’] of char;
样例输入：
abcdefghijklmnopqrstuvwxyz s1 s[s1[i]]:=s2[i]
abcdefghijklmnopqrstuvwxyz s2
3 2
1 poison x[i]:=x[i] or x[j]
2 viking
1
1 3
1 4
2 4
4 5
样例输出：
1
各点1s。
30%的数据保证n<=2000，m<=500，p<=2000;
100%的数据保证n<=10000。
m<=5000,p<=50000;
100%的数据保证所有字符串的长度<=100
2、联络（contact）模5第2题联络
【题目描述】
在成功破译了CCF的来信之后，NOIP群决定迎战CCF，但是现在面临一个问题，由于NOIP群的各位成员不在一起，所以现在要开始联系成员。
在我们伟大的NOIP群里已经公示了CCF的来信，一些经常活动的成员得到消息并且已经联系到了部分成员，但是我们是一个组织，不能单独行动，因此必须要听从群主的号令，于是，必须所有成员都要能够直接或间接联系到群主才可以。
为了保密，此次行动不采用网络方式联系，我们有一个只属于群内成员的特殊联系方式，这种方式最大的优点是保密功能极为强大，但是费用也不低，由于我们的经费有限，为了能留出更多的经费前往CCF，我们要在联系过程中尽量节省费用。
你的任务就是编程计算出联系到所有成员的最少的费用以及得到最少费用的方式。
【输入格式】
第一行一个数n，代表一共要联系到的成员有n个，接下来一个n+1行有一个(n+1)*(n+1)的矩阵，第i+1行第j个数代表第i个人与第j个人联系的费用（群主编号为1），然后一个数m，接下来m行，每行两个数i和j，代表第i个人和第j个人已经相互联系到（数据保
证没有环）。
【输出格式】
第一行一个数z，代表最小费用，接下来若干行，
每行两个数x和y，代表要第x个人与第y个人相联系（按顺序输出）。
【样例输入】
4
0 1 2 3 7 for i:=1 to n do
1 0 4 6 10 for j:=i+1 to n do
2 4 0 5 9 inc(t);a[t].b:=I;a[t].e:=j;a[t].w:a[I,j]
3 6 5 0 8
7 10 9 8 0 for i:=1 to t do
2 x:=a[i].b ;y:=a
4 5 x:=get(x); y:=get(y);
2 5 if x<>y then inc(sum,w)
【样例输出】
3
1 2
1 3
【数据范围】
对于40%的数据m<n<=500
对于100%的数据m<n<=1000
数据保证输出不超过231-1。
3、关押罪犯(prison.pas/c/cpp)模35第3题
【问题描述】
S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。
他们之间的关系自然也极不和谐。
很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。
我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。
如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。
公务繁忙的Z市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。
他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。
假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
【输入】
输入文件名为prison.in。
输入文件的每行中两个数之间用一个空格隔开。
第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M 行每行为三个正整数a j，b j，c j，表示a j 号和b j 号罪犯之间存在仇恨，其怨
气值为c j。
数据保证1<aj=<=bj<=N ，0 < cj≤ 1,000,000,000，且每对罪犯组合只出现一次。
【输出】
输出文件prison.out 共1 行，为Z 市长看到的那个冲突事件的影响力。
如果本年内监狱中未发生任何冲突事件，请输出0。
【输入输出样例】
prison.in prison.out
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
3512
【输入输出样例说明】
罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2 号和3 号罪犯引发）。
其他任何分法都不会比这个分法更优。
【数据范围】
对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。
1 2
4 3
6618 1805
2534 3512
12884
28351 1 2
4 3
2534 3512。
