【算法】并查集的介绍与使用

1.并查集的概论

定义：
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

主要构成：
并查集主要由一个整型数组pre[ ]和两个函数find( )、join( )构成。
数组 pre[ ] 记录了每个点的前驱节点是谁，函数 find(x) 用于查找指定节点 x 属于哪个集合，函数 join(x,y) 用于合并两个节点 x 和 y 。

作用：
并查集的主要作用是求连通分支数（如果一个图中所有点都存在可达关系（直接或间接相连），则此图的连通分支数为1；如果此图有两大子图各自全部可达，则此图的连通分支数为2……）

2.用一个故事来引入并查集（“魔法学院的联盟”）

在遥远的阿尔多王国，有一座声名远扬的魔法学院——天星学院。这所学院不仅教授强大的魔法，还拥有许多古老的传说。传说中提到，曾经有一个神秘的魔法师，名叫艾尔文，他发明了一种神奇的魔法工具，叫做“并查集”。

故事发生在天星学院的一个风和日丽的早晨，学院的学生们正忙于准备即将到来的年度魔法比赛。比赛的内容是让学生们组成小组进行各种挑战，争夺“学院最佳团队”的荣誉。

艾伦和他的朋友们被分配到了同一个小组，但在比赛前的准备中，他们发现学院里有多个小组已经相互合作，形成了若干个强大的联盟。这些联盟的存在让他们感到有些困惑，因为他们不知道如何将所有的合作伙伴都联系起来，从而提高自己的团队实力。

就在他们为此感到苦恼时，学院的长者向他们介绍了一种古老的魔法——并查集。长者解释说，并查集是一种强大的魔法工具，可以帮助他们轻松地管理和合并不同的联盟。

艾伦和他的朋友们认真听取了长者的讲解，并决定尝试使用这种魔法。他们发现，并查集的核心在于两个主要操作：

1. 合并（Union）：当两个小组决定合作时，他们可以通过这个操作将两个小组合并成一个更强大的联盟。
2. 查找（Find）：当他们需要知道某个小组是否已经与其他小组在同一个联盟中时，可以使用这个操作来检查。

使用了并查集的魔法后，艾伦和他的团队发现管理各个小组变得更加简单。他们能够迅速地找到已经存在的联盟，并根据需要进行合并。这使得他们能够更好地协调和组织自己的资源，形成了一个强大的联盟。

随着比赛的进行，艾伦和他的团队利用并查集的魔法成功地将所有的小组整合到一起，形成了一个无敌的联盟。他们在比赛中表现出色，最终赢得了“学院最佳团队”的荣誉。

在获胜的庆祝会上，艾伦和他的朋友们感慨万千，他们深刻理解了并查集魔法的强大力量，也明白了团队合作的重要性。从那以后，天星学院的学生们都学会了如何使用并查集来解决各种复杂的联盟问题，而艾伦和他的团队也因为这次经历成为了学院的传奇人物。

3.从数据结构的方向看并查集

1. 查找（Find）：确定一个元素属于哪个集合，通常返回集合的代表元素或根节点。此操作可以通过路径压缩优化，使得树的高度保持较小，从而提高查找效率。

2. 合并（Union）：将两个集合合并为一个集合。合并操作可以通过按秩合并（按树的深度合并）或按大小合并（合并小的树到大的树）来优化，从而保持数据结构的效率。

并查集常用于处理动态连通性问题，例如在图论中的连通分量计算。通过这些操作，并查集能够在接近常数时间内完成集合的合并和查找。

3.find（）函数的定义与实现

find() 函数用于确定一个元素所在的集合的代表元素或根节点。它通常通过路径压缩优化来提高效率。

开始时每个集合都是一个独立的集合,并且都是等于自己本身下标的数
例如:
p[5]=5,p[3]=3;

如果是M操作的话那么就将集合进行合并,合并的操作是:
p[3]=p[5]=5;
所以3的祖宗节点便成为了5
此时以5为祖宗节点的集合为{5，3}
如果要将p[9]=9插入到p[3]当中,应该找到3的祖宗节点,
然后再把p[9]=9插入其中,所以p[9]=find(3);(find()函数用于查找祖宗节点)
也可以是p[find(9)]=find(3),因为9的节点本身就是9
此时以5为祖宗节点的集合为{5,3,9};
如果碰到多个数的集合插入另一个集合当中其原理是相同的

例如:
上述中以5为祖宗节点的是p[5],p[3],p[9];(即p[5]=5,p[3]=5,p[9]=5)
再构造一个以6为祖宗节点的集合为{6,4，7，10}
如果要将以6为祖宗节点的集合插入到以5为祖宗节点的集合,则该操作可以是
p[6]=find(3)（或者find(9),find(5)）
此时p[6]=5
当然如果是以6为祖宗节点集合中的4,7,10则可以这样
p[find(4)]=find(3)
或者p[find(7)]=find(3)均可以
此时以6为祖宗节点的集合的祖宗节点都成为了5

3.2find（）函数的实现

第一个find函数同时也运用了状态压缩即：

find 函数不仅有找祖宗的功能，还把这个查找路径上所有节点直接变成了祖宗节点的孩子

int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);/*经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:p[x]=x;*/return p[x];//找到了便返回祖宗节点的值
}2.
int find(int x)					//查找x的祖宗结点
{while(pre[x] != x)			//如果x的上级不是祖宗节点x = pre[x];				//x继续找return x;					
}

4.合并集合的代码实现与逻辑

• 先查找两个元素 x 和 y 的根节点。
• 比较两个根节点的秩（高度），将秩较小的根节点的树合并到秩较大的根节点的树下，确保树的高度尽可能低。
• 如果两个根节点的秩相同，将其中一个根节点设置为另一个根节点的子节点，并将该根节点的秩加一。

//合并a b所在的两个集合
void merge(int a, int b)
{int pa = find(a);//找到 a 所在集合的代表元素int pb = find(b);//找到 b 所在集合的代表元素if(pa != pb)//如果不是同一个，则属于不同集合，需要合并{p[pa] = pb;//将a所在集合代表元素的代表元素设置为b所在集合的代表元素。}
}

5.并查集的测试代码（进行了按秩合并的写法）

#include <vector>
#include <iostream>class DisjointSet {
public:DisjointSet(int size) : parent(size), rank(size, 1) {// 初始化每个元素的父节点指向自己for (int i = 0; i < size; ++i) {parent[i] = i;}}// 查找元素 x 所在集合的根节点，并进行路径压缩int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}// 合并两个集合void unionSets(int x, int y) {int rootX = find(x); // 查找 x 的根节点int rootY = find(y); // 查找 y 的根节点if (rootX != rootY) {// 按秩合并：将秩较低的树合并到秩较高的树下if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX] += 1;}}}private:std::vector<int> parent; // 记录每个元素的父节点std::vector<int> rank;   // 记录每个树的秩
};int main() {DisjointSet ds(10); // 初始化一个包含10个元素的并查集ds.unionSets(1, 2); // 合并集合 {1} 和 {2}ds.unionSets(2, 3); // 合并集合 {1, 2} 和 {3}ds.unionSets(4, 5); // 合并集合 {4} 和 {5}// 检查合并后的结果std::cout << "Find 1: " << ds.find(1) << std::endl; // 输出 1std::cout << "Find 3: " << ds.find(3) << std::endl; // 输出 1std::cout << "Find 4: " << ds.find(4) << std::endl; // 输出 4std::cout << "Find 5: " << ds.find(5) << std::endl; // 输出 4ds.unionSets(3, 5); // 合并集合 {1, 2, 3} 和 {4, 5}// 检查合并后的结果std::cout << "Find 5 after union with 3: " << ds.find(5) << std::endl; // 输出 1，因为 1 和 5 现在在同一集合中return 0;
}

6.简单的实现代码（没有使用按秩合并的写法）

#include <vector>
#include <iostream>class DisjointSet {
public:DisjointSet(int size) : parent(size) {for (int i = 0; i < size; ++i) {parent[i] = i; // 每个元素的父节点初始化为自身}}// 查找元素 x 所在集合的根节点，并进行路径压缩int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}// 合并 a 和 b 所在的两个集合void merge(int a, int b) {int rootA = find(a); // 查找 a 所在集合的代表元素int rootB = find(b); // 查找 b 所在集合的代表元素if (rootA != rootB) {parent[rootB] = rootA; // 直接将 b 的根节点挂到 a 的根节点下}}private:std::vector<int> parent; // 记录每个元素的父节点
};int main() {DisjointSet ds(10); // 初始化一个包含10个元素的并查集ds.merge(1, 2); // 合并集合 {1} 和 {2}ds.merge(2, 3); // 合并集合 {1, 2} 和 {3}ds.merge(4, 5); // 合并集合 {4} 和 {5}// 检查合并后的结果std::cout << "Find 1: " << ds.find(1) << std::endl; // 输出 1std::cout << "Find 3: " << ds.find(3) << std::endl; // 输出 1std::cout << "Find 4: " << ds.find(4) << std::endl; // 输出 4std::cout << "Find 5: " << ds.find(5) << std::endl; // 输出 4ds.merge(3, 5); // 合并集合 {1, 2, 3} 和 {4, 5}// 检查合并后的结果std::cout << "Find 5 after union with 3: " << ds.find(5) << std::endl; // 输出 1，因为 1 和 5 现在在同一集合中return 0;
}

7.一些基本操作的实现

const int  N=1005					//指定并查集所能包含元素的个数（由题意决定）
int pre[N];     					//存储每个结点的前驱结点 
int rank[N];    					//树的高度 
void init(int n)     				//初始化函数，对录入的 n个结点进行初始化 
{for(int i = 0; i < n; i++){pre[i] = i;     			//每个结点的上级都是自己 rank[i] = 1;    			//每个结点构成的树的高度为 1 } 
}
int find(int x)     	 		    //查找结点 x的根结点 
{if(pre[x] == x) return x;  		//递归出口：x的上级为 x本身，则 x为根结点 return find(pre[x]); 			//递归查找 
} int find(int x)     				//改进查找算法：完成路径压缩，将 x的上级直接变为根结点，那么树的高度就会大大降低 
{if(pre[x] == x) return x;		//递归出口：x的上级为 x本身，即 x为根结点 return pre[x] = find(pre[x]);   //此代码相当于先找到根结点 rootx，然后 pre[x]=rootx 
} bool isSame(int x, int y)      		//判断两个结点是否连通 
{return find(x) == find(y);  	//判断两个结点的根结点（即代表元）是否相同 
}bool join(int x,int y)
{x = find(x);						//寻找 x的代表元y = find(y);						//寻找 y的代表元if(x == y) return false;			//如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并，返回 false，表示合并失败；否则，执行下面的逻辑if(rank[x] > rank[y]) pre[y]=x;		//如果 x的高度大于 y，则令 y的上级为 xelse								//否则{if(rank[x]==rank[y]) rank[y]++;	//如果 x的高度和 y的高度相同，则令 y的高度加1pre[x]=y;						//让 x的上级为 y}return true;						//返回 true，表示合并成功
}