并查集
并查集
1、概念
并查集(Union-Find)是一种可以用来判断同属一个集合中相互关联的元素属于几个集合，也可以用来判断图结构中的两点是否是连通, 它也是一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
2、根据人找编号 / 根据编号找人（简单介绍一下并查集）
（1）代码展示
// UnionFindSet.h
#pragma once
#include <vector>
#include <map>
template <class T>
class UnionFindSet
{
private:
std::vector<T> _a; // 编号找人
std::map<T, int> _indexmap; // 人找编号的映射关系
public:
UnionFindSet(const T* a, size_t n)
{
for (size_t i = 0; i < n; i++)
{
_a.push_back(a[i]); // 将传进来的值存入到vector中
_indexmap[a[i]] = i; // 映射关系
}
}
};
// photo.cpp
#include <iostream>
#include "UnionFindSet.h"
int main()
{
std::string s[] = { "张三", "李四", "王五", "赵六" };
UnionFindSet<std::string> ufs(s, 4);
return 0;
}
（2）调试结果
（3）优化1：小的往大的合并
（4）优化2：压缩路径
// 找根
int FindRoot(int x)
{
int root = x;
while (_ufs[root] >= 0)
{
root = _ufs[root]; // 下标和值的关系
}
// 压缩路径
while (_ufs[x] >= 0)
{
int parent = _ufs[x]; // 提前存一下父亲结点的值
_ufs[x] = root; // 往上找
x = parent;
}
return root;
}
3、并查集操作和演示题目
（1）并查集操作
i、思路
ii、总体代码
class UnionFindSet
{
private:
std::vector<int> _ufs;
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]; // 前面的值+=后面的值
_ufs[root2] = root1; // 更新后面的值为前面的值（双亲根）
}
// 找根
int FindRoot(int x)
{
int parent = x;
while (_ufs[parent] >= 0)
{
parent = _ufs[parent]; // 下标和值的关系
}
return parent;
}
// 判断是否是同一个树
bool IsSet(int x1, int x2)
{
return FindRoot(x1) == FindRoot(x2);
}
// 算树的数量
int Size()
{
int n = _ufs.size();
int size = 0;
for (int i = 0; i < n; i++)
{
if (_ufs[i] < 0)
{
size++;
}
}
return size;
}
};
（2）演示题目：省份数量
i、做法一：自己写一个并查集
class UnionFindSet
{
private:
std::vector<int> _ufs;
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]; // 前面的值+=后面的值
_ufs[root2] = root1; // 更新后面的值为前面的值（双亲根）
}
// 找根
int FindRoot(int x)
{
int parent = x;
while (_ufs[parent] >= 0)
{
parent = _ufs[parent]; // 下标和值的关系
}
return parent;
}
// 判断是否是同一个树
bool IsSet(int x1, int x2)
{
return FindRoot(x1) == FindRoot(x2);
}
// 算树的数量
int Size()
{
int n = _ufs.size();
int size = 0;
for (int i = 0; i < n; i++)
{
if (_ufs[i] < 0)
{
size++;
}
}
return size;
}
};
class Solution
{
public:
int findCircleNum(vector<vector<int>>& isConnected)
{
UnionFindSet ufs(isConnected.size());
for (int i = 0; i < isConnected.size(); i++)
{
for (int j = 0; j < isConnected[i].size(); j++)
{
if (isConnected[i][j] == 1)
{
ufs.Union(i, j);
}
}
}
return ufs.Size();
}
};
ii、做法二：手动版本
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 (int i = 0; i < isConnected.size(); i++)
{
for (int 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 n = 0;
for (auto e : ufs)
{
if (e < 0)
n++;
}
return n;
}
};
（3）演示题目：等式方程可满足性
进行两次遍历，第一次遍历假如说是中间是等号的情况下的话，就将俩字母都放到同一个集合中，第二次遍历假如说是中间是不等号的情况下的话，就判断俩字母是否是在同一个集合中，在的话就返回false，不在的话就返回true。
class Solution
{
public:
bool equationsPossible(vector<string>& equations)
{
vector<int> ufs(26, -1);
// lambda表达式
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;
}
}
}
// 第二遍遍历，遇到相同的俩字母在一个集合中就返回false
for (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;
}
};
