并查集是一种树型的数据结构，用于处理一些不相集合的合并及查询问题。常常在使用中以森林来表示。
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-findset)。
比如现在有这样的情况：
目前饭局有10个人，没两个人之间都可能存在远方亲戚关系，如何将个人分成不同的家庭？现在将个人编号为{0,1,2,3,4,5,6,7,8,9}
-1表示假设每个人之间都不存在亲戚关系
接下来，饭局中的人互相交谈，了解到自己的亲戚关系，因此可以形成不同的家庭。比如：当前是s1：{0,6,7,8},s2：{1,4,9},s3：{2,3,5}形成了不同的家庭。
用树模型表示
因此规定并查集数组有下面的规定：
如果此时0和1发现也有亲戚关系，那么s1和s2可以合并为一个新的家庭
并查集需要有下面的接口
template<class T>
class UnionFindSet
{
public:
//构造函数
UnionFindSet(){}
//插入元素接口
bool insert(T t);
//查找所属集合
int Findroot(T t);
//合并两个集合
void Union(T t1,T t2);
//统计并查集中一个有多少个集合
size_t count();
private:
unordered_map<T, int> mp; //存放内容和下标的对应关系
unordered_map<int, T>mpt; //存放下标和存放内容的对应关系
vector<int>_fa; //存放父亲下标的数组
}
在vector容器中插入新的元素，并作为一个单独的集合
bool insert(T t)
{
auto it = mp.find(t);
if (it != mp.end())
{
return false;
}
int size = _fa.size();
mp[t] = size;
mpt[size] = t;
_fa.push_back(-1);
}
int Findroot(T t)
{
auto it = mp.find(t);
if (it==mp.end()){
return -1;
}
int x = mp[t];
int father = _fa[x];
if (father < 0){
return x;
}
string fs = mpt[father];
return _fa[x] = Findroot(fs); //路径压缩
}
void Union(T t1,T t2)
{
if (mp.find(t1) == mp.end() || mp.find(t2)==mp.end())
{
return;
}
int fa1 = Findroot(t1);
int fa2 = Findroot(t2);
if (fa1 != fa2)
{
_fa[fa1] += _fa[fa2];
_fa[fa2] = fa1;
}
}
如果_fa[ x ]的值为负数，那么就属于是一个单独的集合
size_t count(){
int cnt = 0;
for (auto i : _fa){
if (i < 0) {
cnt++;
}
}
return cnt;
}
用饭局找亲戚例子检测并查集。
void test(UnionFindSet<string>&u)
{
u.insert("人0");u.insert("人1");u.insert("人2");u.insert("人3");
u.insert("人4");u.insert("人5");u.insert("人6");u.insert("人7");
u.insert("人8");u.insert("人9");
u.Union("人0", "人6");u.Union("人0", "人7");u.Union("人0", "人8");
u.Union("人1", "人4");u.Union("人1","人9");u.Union("人2", "人3");
u.Union("人2", "人5");
}
int main()
{
UnionFindSet<string> u;
test(u);
size_t x1 = u.Findroot("人7");
size_t x2 = u.Findroot("人3");
cout << x1 << endl;
cout << x2 << endl;
u.Union("人0", "人2");
size_t x3 = u.Findroot("人5");
cout << x3 << endl;
return 0;
}
最后得到目标输出
剑指 Offer II 116. 省份数量 - 力扣（LeetCode）
class Solution {
public:
//查找所属集合
int find(vector<int>&fa,int x){
return fa[x]==x?x:fa[x]=find(fa,fa[x]);
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n=isConnected.size();
vector<int>fa(n,0);
//初始化
for(int i=0;i<n;i++){
fa[i]=i;
}
//union
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(isConnected[i][j]==1){
int fi=find(fa,i),fj=find(fa,j);
if(fi!=fj){
fa[fj]=fi;
}
}
}
}
int cnt=0;
for(int i=0;i<n;i++){
if(i==fa[i]){
cnt++;
}
}
return cnt;
}
};
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
vector<int>fa(26,-1);
auto findroot=[&fa](int x)->int{
while(fa[x]>=0){
x=fa[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){
fa[root2]=root1;
}
}
}
//第二次遍历，如果题目要求俩个字母属于不同的集合，但是在第一次遍历的过程中合并到一个集合中，说明等式方程不满足
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;
}
};
class Solution {
public:
int find(vector<int>f,int x){
return f[x]==x?x:find(f,f[x]);
}
bool validTree(int n, vector<vector<int>> &edges) {
vector<int>f(n);
//初始化并查集，将每一个元素作为一个单独的集合
for(int i=0;i<n;i++){
f[i]=i;
}
for(int i=0;i<edges.size();i++){
int u=edges[i][0],v=edges[i][1];
//寻找两个点的父亲节点
int fu=find(f,u),fv=find(f,v);
//如果此时，父亲节点相同，这成环
if(fu==fv){
return false;
}
else{
f[fv]=fu;
}
}
int cnt=0;
for(int i=0;i<n;i++){
if(f[i]==i){
cnt++;
}
}
return cnt==1;
}
};