高阶数据结构并查集

并查集的概念

将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中反复遇到查询某一个元素属于那个集合的运算，这种抽象的数据类型称为并查集。
主要思想：用集合中的一个元素代表集合。

代码实现

#include<iostream>
#include<vector>
class UnionFindSet
{
public:UnionFindSet(size_t n)//构造函数:_ufs(n,-1){}void Union(int x1,int x2)//合并根{int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (root1 == root2)//如果本身在一个集合就没必要合并了	return;_ufs[root1] += _ufs[root2];//2个下标相加_ufs[root2] = root1;//存一下根的下标}int FindRoot(int x)//查找根{ int parent = x;while (_ufs[parent] >= 0)//说明不是根{parent = _ufs[parent];}return parent;//f返回的编号是负数就是根}bool InSet(int x1, int x2){return FindRoot(x1) == FindRoot(x2);//相等说明同一个根在同一个集合}size_t SetSize()//有几个集合{size_t size = 0;for (size_t i = 0; i < _ufs.size(); ++i){if (_ufs[i] < 0)//判断有几个负数就有几个集合,因为负数是根{++size;}}return size;}private:vector<int> _ufs;//编号找人 
};

LeetCode例题

例题一：
116. 省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中省份的数量。
示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
代码解答：

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {vector<int> ufs(isConnected.size(),-1);//手动函数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;//root2变成root1的孩子,root2的下标存的是root1是0}}}}int n=0;for(auto e: ufs){if(e<0)++n;}return n;}
};

例题二：
990. 等式方程的可满足性
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：“a等于b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

代码解答：

class Solution {
public:bool equationsPossible(vector<string>& equations) {vector<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;//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;}
};