并查集

1.并查集原理

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于统一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集（union-find set）。

比如：某公司今年校招全国总招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不同的学校，起先互不认识，每个学生都是一个独立的小团体，现给这些学生进行编号：{1,2,3,4,5,6,7,8,9}；给以下数组用来存储该小集体，数组中的数字代表：该小集合中具有成员的个数。

毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识了，10个人形成了三个小团体，假设0,1,2分别担任队长，负责大家的出行。

一趟火车之旅后，每个小分队成员就互相熟悉，成为一个朋友圈

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

仔细观察数组内情况，可以得出以下结论：

1. 数组的下标对应集合元素的编号。
2. 数组中如果为负数，负数代表根，数字代表该集合中元素个数
3. 数组中如果为非负数，代表该元素双亲在数组中的下标。

在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹的走在了一起，两个小圈子的学生相互介绍，最后成为了一个小圈子：

现在0集合有7个人，2集合有3个人，总共两个朋友圈。

通过以上例子可知，并查集一般可以解决以下问题：

1.查找元素属于那个集合

沿着数组表示树形关系以上一直找到根（树中元素为负数的位置）

2.查看两个元素是否属于同一个集合

沿着数字表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在

3.将两个集合归并成一个集合

将两个集合中的元素合并，将一个集合名称改成另一个集合的名称。

4.集合的个数

遍历数组，数组中元素为负数的个数即为集合的个数。

2. 并查集的模拟实现

#pragma once #include<iostream> #include<vector> using namespace std; class UnionFind { public: UnionFind(int n) : _v(n, -1) //用n个数初始化 {} int FindRoot(int index) { int root = x; while (_v[root] >= 0) { root= _v[root];//数组中存的就是当前数的父亲节点 } //路径压缩 while(_v[x] >= 0) { int parent = _v[x]; _v[x] = root; x = parent; } return root; } void Union(int x1, int x2)//合并 { int root1 = FindRoot(x1); int root2 = FindRoot(x2); if(root1 == root2) return; if(abs(_v[root1]) < abs(_v[root2])) //控制数据量小的往大的集合合并 { swap(root1, root2); } _v[root1] += _v[root2]; //根节点加等上当前节点的值 _v[root2] = root1; //当前节点的值指向父亲 } size_t SetCount()//有多少棵树 { size_t count = 0; for (size_t i = 0; i < _v.size(); i++) { if (_v[i] < 0) count++; } return count; } private: vector<int> _v; };

3.与并查集相关的题

LCR 116. 省份数量 - 力扣（LeetCode）

class UnionFind { public: UnionFind(int n) : _v(n, -1) //用n个数初始化 {} int FindRoot(int index) { while (_v[index] >= 0) { index = _v[index];//数组中存的就是当前数的父亲节点 } return index; } void Union(int x1, int x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); if (root1 != root2) { _v[root1] += _v[root2]; //根节点加等上当前节点的值 _v[root2] = root1; //当前节点的值指向父亲 } } size_t SetCount()//有多少棵树 { size_t count = 0; for (size_t i = 0; i < _v.size(); i++) { if (_v[i] < 0) count++; } return count; } private: vector<int> _v; }; class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { UnionFind u(isConnected.size()); for(int i = 0; i < isConnected.size(); i++) { for(int j = 0; j < isConnected[0].size(); j++) { if(isConnected[i][j] == 1) { u.Union(i, j);//相连就合并这两个城市 } } } return u.SetCount(); } };

990. 等式方程的可满足性 - 力扣（LeetCode）

下面使用并查集，第一次循环先把所有的树给找到，然后第二次循环判断它们是否在同一个树里面。

class Solution { public: bool equationsPossible(vector<string>& equations) { vector<int> ufs(26, -1); auto findroot = [&ufs](int x) { while(ufs[x] >= 0) x = ufs[x]; return x; }; for(int i = 0; i < equations.size(); i++) { if(equations[i][1] == '=') { int root1 = findroot(equations[i][0] - 'a'); int root2 = findroot(equations[i][3] - 'a'); if(root1 != root2) { ufs[root1] += ufs[root2]; ufs[root2] = root1; } } } for(int i = 0; i < equations.size(); i++) { if(equations[i][1] == '!') { int root1 = findroot(equations[i][0] - 'a'); int root2 = findroot(equations[i][3] - 'a'); if(root1 == root2) { return false; } } } return true; } };