并查集

首先要明确的是并查集是森林。由多棵树组成。

并查集 （英文：Disjoint-set data structure，直译为不交集数据结构），用于处理一些 不交集 （Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。

并查集支持如下操作：1、查询：查询某个元素属于哪个集合，通常是返回集合内的一个"代表元素"。这个操作是为了判断两个元素是否在同一个集合之中。2、合并：将两个集合合并为一个。3、添加 ：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。这个数据结构同时支持查询和合并这两种操作。

问题：给了一堆类型为string的数据，应该怎么给他们编号呢？怎么建立对应的映射关系呢？

1、通过编号找数据。把这堆数据存到vector结构里，每个数据就有了自己的编号；2、通过数据找编号。把数据存到map结构中，就可以快速通过编号找到数据。

问题：如何描述数据之间的关系呢？怎么去建立这棵树？

某一部分属性相同的数据归到一个集合里。每个集合中任选一个节点去做根，这个集合中其他的节点作孩子。

题外话：与堆类似（用数组来当底层的数据结构），并查集用数组来表示多棵树，用数组下标来表示关系。用的是双亲表示法，保存父节点的下标即可。B树用的是三叉链。

原理

一个例子：某实习组招生10人，哈尔滨招4人，云南招3人，西藏招3人，10个人来自不同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个数。

 我  你  他   双  时   而  先  句   吃  高 //学生姓名0   1   2   3   4   5   6   7   8   9 //挨个放入vector，人名映射数组编号
-1  -1  -1  -1  -1  -1  -1  -1  -1  -1 //数组--表示该小集体成员个数

数组的初始值给的是-1，表示10个数据每个数据分别是一个集合，集合内无成员。

比如“我”和“先”在一个集合，假设"我"做根，那“我”对应的数组值-1加上"先"对应的-1，得-2，"先"映射的数据编号为6，其对应的数组值改为"我"映射的数据编号0。

 我  你  他   双  时   而  先  句   吃  高 //学生姓名0   1   2   3   4   5   6   7   8   9 //人名映射数组编号
-2  -1  -1  -1  -1  -1   0  -1  -1  -1 //数组

接下来大家结伴去实习地。哈尔滨学生小分队s1={“我”, “先”, “句”, “吃”}，云南学生小分队s2={“你”, “时”, “高”}，西藏学生小分队s3={“他”, “双”, “而”}就相互认识了，10个人形成了三个小团体。假设右三个群主“我”, “你”, “他”担任队长，负责大家的出行。

根据刚才讲解的"我"和"先"组成一个集合的方法，给这10个人组成的3个集合进行分类，最后得到的情况如下

 我  你  他   双  时   而  先  句   吃  高 //学生姓名0   1   2   3   4   5   6   7   8   9 //人名映射数组的下标
-4  -3  -3   2   1   2   0   0   0   1 //数组

从上列表可以看出：编号6, 7, 8同学属于0号小分队，该小分队中有4人(包含队长0)；编号为4和9的同学属于1号小分队，该小分队有3人(包含队长1)，编号为3和5的同学属于2号小分队，该小分队有3个人(包含队长1)。

仔细观察数组中内融化，可以得出以下结论：

1. 数组的下标表示学生姓名和数组的映射关系；
2. 数组的值如果为负数，那么这个位置映射的学生就是集合的代表数据（树的根），该数字的绝对值代表该集合中元素个数；
3. 数组的值如果为非负数，这个值表示该元素的父亲在数组中的下标；

实习一段时间后，哈尔滨小分队和云南小分队相互认识，最后合并为一个集合。

 我  你  他   双  时   而  先  句   吃  高 //学生姓名0   1   2   3   4   5   6   7   8   9 //人名映射数组的下标
-7   0  -3   2   1   2   0   0   0   1 //数组

此时将云南小分队的队长"你"加入到"我"的集合中，只需要修改"我"和"你"对应的数组的值即可。现在"我"集合有7个人，"他"集合有3个人，总共2个集合。

功能

通过以上例子可知，沿着数组表示的树形关系可以找到根。并查集一般可以解决一下问题：

1. 查找元素属于哪个集合：根据数组的值（即根据该值表示的是树形结构里的父亲节点下标）一直找到根(当数组值为负数就是根)；
2. 查看两个元素是否属于同一个集合：根据数组的值一直找到树的根，如果根相同表明在同一个集合，否则不在同一个集合；
3. 将两个集合归并成一个集合：a.将两个集合中的元素合并；b.将一个集合名称改成另一个集合的名称；
4. 集合的个数：遍历数组，数组中元素为负数的个数即为集合的个数。

优化

路径压缩

我们在合并集合的时候，是将根节点编号大的树直接当作另一颗根节点编号小的树的子树（合并的这个集合层数就会越来越多）。当合并的集合多了的话，我们在找根的时候，每次找根都要一层一层地往上找，效率会低。

此时的优化方法就是在查找根的时候，进行压缩。举例：查找x的时候，发现找到根的时候x在数组里的值（现在的父亲不等于根），就把x在数组中对应的值改成最终找到的根的下标。

// 优化2：路径压缩
int FindRoot(int index)
{// 树形结构 存储的是父节点的下标int root = index;// 如果当前下标对应的值>=0，说明她们不是根，要继续查找while (_ufs[root] >= 0) root = _ufs[root];// 路径压缩while (_ufs[index] >= 0){int parent = _ufs[index];// 走过的每个节点都成为根的孩子_ufs[index] = root;index = parent;}return root;
}
// 合并元素 -- 合并原则：按根节点下标的大小
bool Union(int x1, int x2)
{int root1 = FindRoot(x1);//找到下标为x1的根节点int root2 = FindRoot(x2);//找到下标为x2的根节点// x1已经与x2在同一个集合（根节点一样，说明在同一个集合）if (root1 == root2)return false;// 把下标大的根节点往下标小的根节点集合去合并if (root1 > root2)swap(root1, root2);// 将两个集合中元素合并_ufs[root1] += _ufs[root2];// 将其中一个集合名称改变成另外一个_ufs[root2] = root1;return true;
}

启发式压缩：优化合并原则

启发式压缩就是边合并的时候边优化。将合并原则修改为：按所在集合元素多少来合并，把数据少的小集合合并到数据多的大集合去

// 优化1：优化合并原则
int FindRoot(int index)
{//树形结构 存储的是父节点的下标int parent = index;//如果当前下标对应的值>=0，说明她们不是根，要继续查找while (_ufs[parent] >= 0) parent = _ufs[parent];return parent;
}
//合并元素 合并原则：按所在集合元素多少
bool Union(int x1, int x2)
{int root1 = FindRoot(x1);//找到下标为x1的根节点int root2 = FindRoot(x2);//找到下标为x2的根节点// x1已经与x2在同一个集合（根节点一样，说明在同一个集合）if (root1 == root2)return false;//把数据量小的往大集合去合并if(abs(_ufs[root1]) < abs(_ufs[root2]))swap(root1, root2);// 将两个集合中元素合并_ufs[root1] += _ufs[root2];// 将其中一个集合名称改变成另外一个_ufs[root2] = root1;return true;
}

当然，把这两种优化方法结合起来，优化效果更好！找根的时候就不用层层往回找了。

代码

基础版，直接使用数据的编号来操作

#include <iostream>
#include <vector>
using namespace std;class UnionFindSet
{
public:UnionFindSet(size_t n):_ufs(n, -1){}// 给一个元素的编号，找到该元素所在集合的名称int FindRoot(int index){//树形结构 存储的是父节点的下标int parent = index;//如果当前下标对应的值>=0，说明她们不是根，要继续查找while (_ufs[parent] >= 0) parent = _ufs[parent];return parent;}//合并元素bool Union(int x1, int x2){int root1 = FindRoot(x1);//找到下标为x1的根节点int root2 = FindRoot(x2);//找到下标为x2的根节点// x1已经与x2在同一个集合（根节点一样，说明在同一个集合）if (root1 == root2)return false;// 将两个集合中元素合并_ufs[root1] += _ufs[root2];// 将其中一个集合名称改变成另外一个_ufs[root2] = root1;return true;}//集合个数size_t Count()const{int count = 0;//如果当前下标对应的值<0，说明是根，就表示一个集合for (auto e : _ufs){if (e < 0) count++;}return count;}//判断两个数据是否在同一个集合里bool InSet(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}
private:vector<int> _ufs;
};

升级版，需要自己建立数据和下标的映射关系

#pragma once#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;template<class T>
class Set
{
public:Set(const T* a, size_t n){for (size_t i = 0; i < n; ++i){_a.push_back(a[i]);//给每个数据进行编号_indexMap[a[i]] = i;//将数据和编号建立映射关系}}vector<T> _a;//根据编号找数据。先将数据存到vector结构体里，每个数据就有了自己的编号map<T, int> _indexMap;//根据数据找编号
};template<class T>
class UnionFindSet
{
public:int getIndex(const T& key){auto it = _set._indexMap.find(key);if (it == _set._indexMap.end()){cout << "查无此人, 请重新输入" << endl;exit(1);}return it->second;}UnionFindSet(Set<T>& set):_set(set), _ufs(set._a.size(), -1){}// 给一个元素的编号，找到该元素所在集合的名称T FindRoot(const T& name){int num = getIndex(name);while (_ufs[num] >= 0) num = _ufs[num];//找到根的编号了return _set._a[num];}// 求集合的个数，即数组中负数的个数size_t Count()const{size_t count = 0;for (auto& e : _ufs){if (e < 0) ++count;}return count;}// 合并集合bool Union(const T& name1, const T& name2){T root1 = FindRoot(name1);T root2 = FindRoot(name2);//两个数据已经在同一个集合里了if (root1 == root2) return false;//合并 把第二个集合 合并 到第一个集合里int num1 = getIndex(name1);int num2 = getIndex(name2);// 找到第二个集合的根while (_ufs[num2] >= 0) num2 = _ufs[num2];_ufs[num1] += _ufs[num2];_ufs[num2] = num1;return true;}
private:Set<T> _set;vector<int> _ufs;
};

题目

剑指 Offer II 116. 省份数量

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {vector<int> ufs(isConnected.size(), -1);//lambda表达式auto findRoot = [&ufs](int x){while(ufs[x] >= 0) x = ufs[x];return x;};for(size_t i = 0; i < isConnected.size(); ++i){for(size_t j = 0; j < isConnected[i].size(); ++j){if(isConnected[i][j] == 1)//表示城市有连接，可以进入一个集合{int root1 = findRoot(i);int root2 = findRoot(j);if(root1 != root2){ufs[root1] += ufs[root2];ufs[root2] = root1;}                    }}}int count = 0;for(auto e: ufs){if(e < 0) count++;}return count;}
};

990. 等式方程的可满足性

class Solution {
public:bool equationsPossible(vector<string>& equations) {//相等的值 就在一个集合中，不相等的值不能在 tvector<int> ufs(26, -1);//26个字母auto findRoot = [&ufs](int x){while(ufs[x] >= 0) x = ufs[x];return x;};// 第一遍，先把相等的值加到一个集合中for(auto& str : equations){if(str[1] == '='){int root1 = findRoot(str[0] - 'a');int root2 = findRoot(str[3] - 'a');if(root1 != root2){ufs[root1] += ufs[root2];ufs[root2] = root1;}}}// 第二遍，先看不相等的值在不在一个集合，如果在，就返回falsefor(auto& str : equations){if(str[1] == '!'){int root1 = findRoot(str[0] - 'a');int root2 = findRoot(str[3] - 'a');if(root1 == root2){return false;}}}return true;}
};

西交大教育在线