并查集的原理
来自百度百科
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始的时候让每个元素构成单个元素的集合，然后按一定顺序讲属于同一组的元素所在集合合并，期间要反复查询一个元素在哪个集合中。描述改问题的抽象数据结构为并查集。 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
对于并查集的操作
- 初始化：对于初始化，我们都把每个元素初始化为-1。在并查集中，负数表示根节点，它的绝对值表示以它为根的集合有多少元素。非负表示根节点的下标
- 查找：查找元素所在的集合，即根节点
- 合并：将两个元素所在的集合合并为一个集合。在合并之前要判断两个元素是否属于同一个集合。
并查集的实现
对于并查集的实现我们就要先确定它的存储类型——即到底用什么存储它
这里我们用数组的形式进行存储——类似于堆的存储形式
那么对于该数据结构,其成员变量设成vector<int>注意的是：下标是实际的值，存储的是根节点的下标或者是以该节点为根的个数
#include <vector>
class UnionSet
{
vector<int> _us;
public:
UnionSet(const int size)
:_us(size,-1){}
//
};成员方法：查找
查找就是查找根节点——负数就是根——返回是下标
int Find(int x)
{
while (_us[x] >= 0)
{
x = _us[x];
}
return x;
}成员方法：合并
把两个集合进行合并，进行合并那么就要找到该值对应的根，然后进行下面的操作
可以以根所对应的那个为新集合的根，根所对应的值大的为孩子。
操作方法就是值相加给小的，大的指向小的
同时要注意：如果是属于同一个集合
void Union(int x,int y)
{
int root1 = Find(x);
int root2 = Find(y);
if (root1 < root2) {
_us[root1] += _us[root2];
_us[root2] = root1;
}
else if (root1 > root2) {
_us[root2] += _us[root1];
_us[root1] = root2;
}
}计算有多少个集合——只需要查看有几个小于0的就可以了
int SetCount()
{
int ret = 0;
for (auto x : _us)
{
if (x < 0)
ret++;
}
return ret;
}路径压缩，以后再写
时间复杂度O(N)
并查集的应用
省份数量：
https://leetcode.cn/problems/bLyHh0/description/
class UnionSet
{
vector<int> _us;
public:
UnionSet(const int size)
:_us(size,-1){}
//
int Find(int x)
{
while (_us[x] >= 0)
{
x = _us[x];
}
return x;
}
void Union(int x,int y)
{
int root1 = Find(x);
int root2 = Find(y);
if (root1 < root2) {
_us[root1] += _us[root2];
_us[root2] = root1;
}
else if (root1 > root2) {
_us[root2] += _us[root1];
_us[root1] = root2;
}
}
int SetCount()
{
int ret = 0;
for (auto x : _us)
{
if (x < 0)
ret++;
}
return ret;
}
};
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n=isConnected.size();
UnionSet uset(n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(isConnected[i][j]==1){
uset.Union(i,j);
}
}
}
return uset.SetCount();
}
};其实按上面那么写不是很方便，还有单独弄一个类。
可以用下面的方法：其实就是把上面的类进行拆分了
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<int> unionset(n,-1);
auto f=[&](int i,int j){
while(unionset[i]>=0)
i=unionset[i];
while(unionset[j]>=0)
j=unionset[j];
if(i!=j)
{
unionset[i]+=unionset[j];
unionset[j]=i;
}
};
//自己写一个合并
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(isConnected[i][j]==1)
f(i,j);
}
}
//自己写一个查询
int ret=0;
for(auto x:unionset)
{
if(x<0)
ret++;
}
return ret;
}
};等式方程的可满足性
https://leetcode.cn/problems/satisfiability-of-equality-equations/description/
- 先把相等的到放入同一个集合，把所有的集合构造完成
- 不相等的进行查询是不是属于同一个集合，如果属于就为
false。
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
vector<int> unionset(26,-1);
auto find=[&](int i){
while(unionset[i]>=0){
i=unionset[i];
}
return i;
};
for(auto& str:equations)
{
int root1 = find(str[0]-'a');
int root2 = find(str[3]-'a');
if(str[1]=='='){
if(root1!=root2)
{
unionset[root1]+=unionset[root2];
unionset[root2]=root1;
}
}
}
for(auto& str:equations)
{
int root1 = find(str[0]-'a');
int root2 = find(str[3]-'a');
if(str[1]=='!'){
if(root1==root2)
return false;
}
}
return true;
}
};