[数据结构#1] 并查集 | FindRoot | Union | 优化

template<class T>
class UnionFindSet
{
public:
UnionFindSet(const T* a, size_t sz)
{
    for (int i = 0; i < sz; ++i)
        {
            _a.push_back(a[i]);//将数组中元素添加到vector中
            _IndexMap[a[i]] = i;//将人映射到hash中
        }
}


private:
vector<T> _a;          //编号找人
map<T, int> _IndexMap; //人找编号
};

int main()
{
    string arr[] = { "张三","李四","王五","赵六" };
    UnionFindSet<string> ufs(arr, 4);
    return 0;
}

_a.push_back(a[i]);：这一行代码将数组 a 的第 i 个元素添加到成员变量 _a 向量的末尾。这里 a 是构造函数参数中的一个指针，指向传入的数组，而 a[i] 则是该数组中第 i 个位置的元素。
_IndexMap[a[i]] = i;：此行代码则是在建立一个映射关系。它使用成员变量 _IndexMap，这是一个从类型 T 映射到整数类型的关联容器（map）。这里它将数组 a 的第 i 个元素作为键，i 作为值插入到 _IndexMap 中。因此，以后当我们知道某个人的名字时，可以通过 _IndexMap 快速查找这个人在原始数组中的索引位置。

这样不管是给下标还是给名字都可以解决这里的问题。

数据结构设计

并查集通过一个数组表示关系：

数组下标 表示集合中的元素编号。
数组值 用于表示该元素的父节点或根节点的信息。

- 负数：表示集合的根，绝对值为该集合中元素的个数。
- 非负数：表示其父节点在数组中的下标。

双亲表示法：每个节点存储其父节点的位置，通过不断向上查找父节点，最终可以找到集合的根节点。

2. 并查集基本操作

(1) 初始化

初始时，每个元素自成一个集合，数组值均为 -1，表示每个集合的大小为 1。

UnionFindSet(int sz)
    : _ufs(sz, -1) {}  // 初始化，大小为 sz，每个位置存储 -1

(2) 查询根节点 (FindRoot)

找到某个元素所在集合的根节点。
如果当前节点的父节点为负数，则该节点是根节点。
路径压缩：为了提高查询效率，将查询路径上的所有节点直接连接到根节点。

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;
}

这里在补充说一点，并查集路径压缩 的问题。比如集合是下面这个样子，要从9找到根需要跳很多层。影响找根的效率，能不能想到什么办法把路径压缩一下呢？

其实也很简单，反正都是在同一个集合，是不是直接可以考虑把下面的直接压到根的下面做根的孩子。这样就变成了一层。如果数据量很多层数很高压缩路径后这样很不错。

一般在查找根的时候去压缩。
查找谁就把它这一条路径压缩。
找到根之后判断一下，如果它的父亲就是根就不用压缩，如果不是说明中间有间隔层，然后就可以把这条路径压缩。

比如是这个4，首先先把4变成2的孩子，然后将4的父亲1也去变成2的孩子，这条路径都可以变成2的孩子。

(3) 合并集合 (Union)

并查集除了路径压缩，还有一种提高效率的方式，比如两个集合合并的时候

- 小集合向大集合合并，以减少树的深度。

实现步骤：

- 找到两个集合的根节点。
- 如果根节点相同，说明两个元素已在同一个集合中，无需合并。
- 否则，将小集合的根指向大集合的根，并更新集合大小。

bool Union(int x1, int x2) {
    int root1 = FindRoot(x1);
    int root2 = FindRoot(x2);

    if (root1 == root2) return false;

    // 控制小集合向大集合合并
    if (abs(_ufs[root1]) < abs(_ufs[root2])) {
        swap(root1, root2);
    }

    _ufs[root1] += _ufs[root2];
    _ufs[root2] = root1;

    return true;
}

(4) 集合操作总结

查找元素所属集合：找到其根节点。
判断两个元素是否属于同一集合：检查它们的根节点是否相同。
统计集合数量：统计数组中负数的个数，即为集合的数量。

并查集优化

(1) 路径压缩

在查询根节点时，将路径上的节点直接连接到根节点，减少树的高度。
优化后的查找复杂度接近 O(1) 。

(2) 按秩合并

优先将元素较少的集合合并到元素较多的集合，进一步减少树的高度。
实现方法：比较根节点的绝对值，选择小集合向大集合合并。

完整代码：

#pragma once

#include<iostream>
#include<vector>
#include<map>

using namespace std;

//template<class T>
//class UnionFindSet
//{
//public:
//	UnionFindSet(const T* a, size_t sz)
//	{
//		for (int i = 0; i < sz; ++i)
//		{
//			_a.push_back(a[i]);
//			_IndexMap[a[i]] = i;
//		}
//	}
//
//
//private:
//	vector<T> _a;          //编号找人
//	map<T, int> _IndexMap; //人找编号
//};


class UnionFindSet
{
public:
	UnionFindSet(int sz)
		:_ufs(sz,-1)// 初始时，将数组中元素全部设置为1
	{}


	bool Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		// x1已经与x2在同一个集合
		if (root1 == root2)
			return false;

		//控制数据量小的往大的集合合并
		if (abs(_ufs[root1]) < abs(_ufs[root2]))
		{
			swap(root1, root2);
		}

		// 将两个集合中元素合并
		_ufs[root1] += _ufs[root2];

		// 将其中一个集合名称改变成另外一个
		_ufs[root2] = root1;

		return true;
	}

	// 给一个元素的编号，找到该元素所在集合的名称
	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;
	}

	bool IsSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	// 数组中负数的个数，即为集合的个数
	size_t SetSize()
	{
		size_t count = 0;
		for (auto e : _ufs)
		{
			if (e < 0) 
				++count;
		}
		return count;
	}

private:
	vector<int> _ufs;
};

3. 并查集的应用

(1) 统计省份数量

题目链接：[LCR 116. 省份数量]

思路：

- 使用并查集，将直接连接的城市合并到同一个集合。
- 遍历矩阵，统计并查集中集合的数量。

代码实现：

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    vector<int> ufs(n, -1);

    auto Findroot = [&](int x) {
        while (ufs[x] >= 0) {
            x = ufs[x];
        }
        return x;
    };

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (isConnected[i][j] == 1) {
                int root1 = Findroot(i);
                int root2 = Findroot(j);
                if (root1 != root2) {
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            }
        }
    }

    return count_if(ufs.begin(), ufs.end(), [](int x) { return x < 0; });
}

(2) 判断等式方程是否成立

题目链接：[990. 等式方程的可满足性]

思路：

- 将所有“相等”的变量合并到同一个集合。
- 遍历“不等”关系，若两个变量属于同一个集合，则矛盾。

代码实现：

bool equationsPossible(vector<string>& equations) {
    vector<int> ufs(26, -1);

    auto Findroot = [&](int x) {
        while (ufs[x] >= 0) {
            x = ufs[x];
        }
        return x;
    };

    // 合并“相等”关系
    for (auto& eq : equations) {
        if (eq[1] == '=') {
            int root1 = Findroot(eq[0] - 'a');
            int root2 = Findroot(eq[3] - 'a');
            if (root1 != root2) {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        }
    }

    // 检查“不等”关系
    for (auto& eq : equations) {
        if (eq[1] == '!') {
            int root1 = Findroot(eq[0] - 'a');
            int root2 = Findroot(eq[3] - 'a');
            if (root1 == root2) return false;
        }
    }
    return true;
}

这是一道并查集的板子，==号我们可以认为两个字母之间存在一条边，先遍历一遍把所有 == 的字母进行连接，然后再次遍历看一下不相等的字母是否在一个连通分量上，那么主要就是怎么连接以及怎么去判断两个字母是否在同一个连通分量上，这就要用到并查集的知识。
这里推荐一篇博客，讲的挺好的，主要是路径压缩的时候优化了查找的时间。看完之后秒懂并查集。

并查集详解 ——图文解说,简单易懂(转)-CSDN博客

并查集使用场景：两极性的集合划分

连接或不连接，相等或不相等的判断

并查集是一种高效的数据结构，支持快速的合并和查询操作，并在路径压缩和按秩合并优化下性能接近常数时间。

[数据结构#1] 并查集 | FindRoot | Union | 优化 | 应用

1. 并查集原理

问题背景

名称与编号映射