并查集
并查集是一种简单且强大的工具。本文我们就是学习并介绍一下并查集。并查集的资料网上有很多，也有很多代码实现。博主在学习的过程中也查阅了很多资料，有兴趣的话可以Google之。
并查集有三个数据结构：
集合：实际元素组成的集合
类信息：记录元素的类信息
秩信息：记录元素的高度
并查集包含三种基本操作：
Init：初始化，将集合每个元素看做一个类别，元素的类信息即为自身，秩信息都为0
Find：查找，根据给定的元素，返回其类别信息。在执行查找的过程中进行路径压缩优化，以提高后续Find的效率。
Union：合并，将两个元素所在的集合进行合并（集合用其中的元素来表示），在合并的过程中同样进行优化，这里的优化方法为按秩合并。秩低的类别归到秩高类别，这样合并后的树的最大高度做多增加1（只有两个集合的秩相等时，才增加1；否则都不增加）。
下面，我们给出并查集的一种实现。相关说明会在程序注释中解释。
// 并查集 #include <iostream> #include <vector> using namespace std; const int NUM = 101; vector<int> data(101); // 元素集合 vector<int> father(101); // 类别信息 vector<int> mRank(101); // 秩信息 // 初始化并查集 // 初始化n个元素的集合 void Init(int n) { n = n <= NUM ? n : NUM; for (auto i = 0; i != n; ++i) { data[i] = i + 1; father[i] = i; mRank[i] = 0; // 叶子节点高度为0 } } // 查找 // 查找x元素 // 注意，这里的x不是元素的实际值，而是元素的在data中的索引 int Find(int x) { if (x == father[x]) // x为根节点 { return father[x]; } else // x不为根节点 { // return Find(father[x]); // 直接返回，并没有进行路径压缩优化 return father[x] = Find(father[x]); // 进行路径压缩优化 } } // 合并 // 合并的是两个集合（类别） // 两个元素x、y，注意这里x、y不是元素的值，而是其在data中的索引 // 用x、y来表示其所在的集合 // 集合的表示都是用data的索引来表示 // 元素的表示，也都是用data的索引来表示 void Union(int x, int y) { x = Find(x); y = Find(y); if (x == y) // 属于同一个类别，不合并 { return; } // 不是同一个类别 if (mRank[x] > mRank[y]) // 这里的x表示类别，也是节点，rand[x]既是类别的秩也是节点的秩，同理y { father[y] = x; // 将y类别归到x类别 // 不对x的秩进行修改 } else { if (mRank[x] == mRank[y]) { // 由于是将x类别归到y类别，所以对y的秩加1 ++mRank[y]; } father[x] = y; // 将x类别归到y类别 // 不对y的秩进行修改，在y的秩大于x的秩的情况下 } } void Display(int n) { for (auto i = 0; i != n; ++i) { cout << data[i] << ' '; } cout << endl; for (auto i = 0; i != n; ++i) { cout << father[i] << ' '; } cout << endl; for (auto i = 0; i != n; ++i) { cout << mRank[i] << ' '; } cout << endl; } int main() { int n = 9; Init(n); Display(n); cout << Find(5) << endl; cout << Find(8) << endl; Union(5, 8); cout << Find(5) << endl; cout << Find(8) << endl; Union(1, 2); Union(1, 3); Union(8, 1); cout << Find(1) << endl; cout << Find(2) << endl; cout << Find(3) << endl; cout << Find(5) << endl; cout << Find(8) << endl; Display(n); return 0; }
关于程序的说明可以参考注释。
这里我们对集合（类别）和元素的表示进行一下说明。Find函数的作用是查找元素x的所属类别，这里的x不是元素的值，而是元素在data中的索引，也就是说元素是用data的索引来表示的。这里我们无法针对元素的秩，进行Find其类别。
Union函数是合并x和y两个类别，注意，这里的x和y实质上还是data的索引，是用x和y两个元素在data中的索引来表示其各自所属的类别。在Union函数中，x和y有的时候表示元素的索引，有的时候表示类别信息。
个人认为，理解并查集的关键最在于理解元素的表示、类别的表示、元素的索引，以及三者之间的关系。
元素的索引用来表示元素。
元素用来表示其所在的类别，实质上是用元素的索引来表示元素所在的类别。