一. 什么是并查集？
并查集是一种表示元素与集合之间关系的表示型数据结构。其功能主要有两个：
并：合并两个集合。
查：查找两个元素是否在同一个集合。
下面我们假设一个情景：R公司在A高校中招收了10名实习生，一开始这些人都互不认识。我们用一个数组来表示他们之间的关系，其中下标为[0, 9]代表每一位同学的编号，因为他们都互不认识，所以每一个都各自代表一个集合初始时一共有10个集合，他们的值一开始都存-1。
其中下标编号为0、1、2、3的四位同学都来自西安；下标为4、5、6的三位同学来自于云南；下标为7、8、9的三位同学来自北京。公司考虑把来自相同地方的同学编为一组，这样他们就相互认识了。
在物理上我们使用数组来表示这几个同学之间的关系：每个下标存的是该位置直接双亲的下标，根下标存的是一个负值，其绝对值代表该集合的元素个数。
实习过程中来自云南的同学4认识了来自北京的同学8，交流之后才知道他们原来是同一个学校的。
就这样，来自云南和北京的两个集合（六个人）相互认识了，他们变为一个集合，这就是并查集中的“并”功能。
并查集还有一个功能就是查找两个元素是否在一个集合：
二. 如何实现并查集？
通过上面例子我们发现：在逻辑上我们用树表示一个集合，物理上用数组（并查集）来表示一个个元素和所有集合之间的关系。这个数组是个整形数组，下标对应一个个元素，而下标的值存的是它直接父亲的下标、根下标存的是该集合元素总数的负值。
假设给定元素的类型是名字，不是下标编号了，这时该怎么办？创建一个元素类型的数组，让每个元素映射它的下标编号，这样就可以用下标编号代表元素了。
1. 并查集基本框架
成员变量是个整形数组_ufs。构造函数传入数组的长度，通过resize()初始化_ufs令它的值一开始全为-1。
class UnionFindSet { public: UnionFindSet(int n) { _ufs.resize(n, -1); } private: vector<int> _ufs; };
2. 成员函数介绍
2.1 接口一：查找元素的根下标
功能：传入当前元素的下标，返回该元素的根下标。
思路：通过下标逐个地向上的访问，直到值为负数拿到的该下标就是要找的根下标。
int FindRoot(int index) { while(_ufs[index] >= 0) { index = _ufs[index]; } return index; }
2.2 接口二：合并两个元素所在的集合
功能：传入两个元素的下标x1和x2，合并这个元素所在的集合。
思路：先查找的x1和x2的根下标root1、root2，判断它们如果相同说明已经在一个集合中，不用再处理了；如果不相同，合并root1和root2代表的集合。
_ufs[root1] += _ufs[root2]。更新root1下标的值，即合并后的元素个数。
_ufs[root2] = root1。更新root2下标的值为它直接父亲节点的下标root1。
// 查找根下标 int FindRoot(int index) { while(_ufs[index] >= 0) { index = _ufs[index]; } return index; } // 合并两元素所在的个集合 void Union(int x1, int x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); if(root1 != root2) { _ufs[root1] += _ufs[root2]; _ufs[root2] = root1; } }
2.3 接口三：获取集合个数
遍历一遍数组，如果值为负数就代表是一个根下标，也就是一个集合，统计根下标的数量即可。
int GetSet() { int count = 0; for(auto e : _ufs) { if(e < 0) { ++count; } } return count; }
3. 并查集的完整实现代码
class UnionFindSet { public: UnionFindSet(int n) { _ufs.resize(n, -1); } int FindRoot(int index) { while(_ufs[index] >= 0) { index = _ufs[index]; } return index; } void Union(int x1, int x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); if(root1 != root2) { _ufs[root1] += _ufs[root2]; _ufs[root2] = root1; } } int GetSet() { int count = 0; for(auto e : _ufs) { if(e < 0) { ++count; } } return count; } private: vector<int> _ufs; };
三. 为什么要有并查集？
1. 并查集的用途
现实生活中，有两种类型的问题可以借助并查集来解决：
用途1：用来确定无向图中连通子图(集合)的个数。
用途2：用来解决最小生成树的问题。
2. 并查集相关题目总结
下面是一些可以使用并查集来解决的OJ题目
第一题：等式方程的可满足性
题目连接
题目描述：
解题思路：
首先对于每一个小写字母，我们可以通过alpha - ‘a’映射得到对应字母alpha的下标编号。然后分类对每一个关系字符方程进行处理：
先处理“==”的方程，把符号两边的字符统一到一个集合里。
再处理“!=”的方程，反证“!=”符号两边的字符如果在一个集合中就返回false。如果都顺利处理完了就返回true。
完整代码：
// 这里粘贴并查集的实现 class Solution { public: bool equationsPossible(vector<string>& equations) { // 映射26个小写字母和下标[0, 25]之间的关系 UnionFindSet ufs(26); // 1、先把所有==关系的元素集合到一起 for(auto& e : equations) { if(e[1] == '=') { ufs.Union(e[0]-'a', e[3]-'a'); } } // 2、反证：如果!=关系的元素在一个集合中就返回false for(auto& e : equations) { if(e[1] == '!' && (ufs.FindRoot(e[0]-'a') == ufs.FindRoot(e[3]-'a'))) { return false; } } return true; } };
第二题：计算朋友圈
题目连接
题目描述:
假设有N个用户，其中有些人是朋友，有些则不是。A和B是朋友，B和C是朋友，这样ABC就是一个朋友圈，请计算给定的朋友关系的朋友圈数。
给定一个 N * N 的矩阵 M，表示用户之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个人互为朋友关系，否则为不知道。你必须输出所有用户中的已知的朋友圈总数。
输入描述:
第一行输入为表示用户数N
第2到1+N行表示朋友之间关系，如果值为1表示有朋友关系
输出描述:
输出朋友圈数
示例1:
输入
3
1,1,0
1,1,1
0,1,1
输出
1
说明
第0，1，2个用户组成了一个朋友圈
示例2:
输入
3
1,1,0
1,1,0
0,0,1
输出
2
说明
第0个用户和第1个用户组成一个朋友圈，第2个用户组成一个朋友圈
解题思路：
遍历二维数组，如果是朋友就直接通过Union（）把两个因素所在的集合合并，最后通过GetSet（）获取并查集中集合的个数即为朋友圈数量。
注意输入的每个关系之间是用逗号分隔的，在解析时我是通过把每行先转为字符串在拿到数字的。
完整代码：
#include <vector> #include <string> #include <iostream> using namespace std; // 这里粘贴并查集的实现 int main() { int N = 0; cin >> N; UnionFindSet ufs(N); getchar();// 从缓冲区中拿走输入N后遗留下来的'\n' vector<vector<int>> vv(N, vector<int>(N)); for (int i = 0; i < N; ++i) { string s; getline(cin, s); vector<int> tmp; for (auto e : s) { if (e == '0' || e == '1') { tmp.push_back(e-'0'); } } for (int j = 0; j < N; ++j) { vv[i][j] = tmp[j]; if (vv[i][j] == 1) { ufs.Union(i, j); } } } cout << ufs.GetSet() << endl; return 0; }
