🍑个人主页：Jupiter. 🚀 所属专栏：高阶数据结构 欢迎大家点赞收藏评论😊

---

并查集原理

• 在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。

假设有10个元素，如下所示：0~9为元素值，-1是初始化的值。

现在他们被分为三个小组：0 6 7 8 为一组，0为组长 ；1 4 7 一组，1为组长 ； 2 3 5一组，2为组长；如下集合树的表示：

• 数组的下标对应集合中元素的编号
• 数组中如果为负数，负号代表根，数字代表该集合中元素个数
• 数组中如果为非负数，代表该元素双亲在数组中的下标

现在假设集合0ui集合1要合并，只需要将元素0的内容加上元素1的内容（-4 + -3 = -7），将元素1的内容改为元素0的下标，也就是0；如下图：

常见操作

• 查找（Find）：确定元素所属的集合（通常返回根节点）。
• 合并（Union）：将两个元素所在的集合合并为一个集合。
• 计数（Count）：计算一共有多少个集合。

关键操作与优化

路径压缩（Path Compression）

• 在查找时，将节点直接指向根节点，缩短后续查询路径，使树更扁平。
• 示例：find(x) 时，递归或迭代地将路径上的所有节点父指针指向根。

按秩合并（Union by Rank/Height）

• 合并时，将较矮的树挂到较高树的根下，避免树过高。
• 维护一个rank数组记录树的高度，合并时比较根节点的rank。

查找（Find）代码及解析

//查找它所属集合的根  带路径压缩的代码  循环版本
int FindRoot(int index)
{
	while (_ufs[index] >= 0)
	{
		_ufs[index] = _ufs[_ufs[index]];
		index = _ufs[index];
	}

	return index;
}

// 查找根节点（带路径压缩）   递归版本
int FindRoot(int index)
{
	if (_ufs[index] >=0)
	{
		_ufs[index] = FindRoot(_ufs[index]);  // 递归路径压缩
	}
	return _ufs[index];
}

合并（Union）代码及解析

	//给两个下标，将两个标所属的集合合并成一个集合
	bool Union(int index1,int index2)
	{
		int root1 = FindRoot(index1);
		int root2 = FindRoot(index2);

		//属于同一个集合  直接返回
		if (root1 == root2) return false;

		//第一种情况：root1的高度大于root2，直接将root2合并到root1上，并且因为root1高度小于root2.合并并不会导致高度增加
		if (_height[root1] > _height[root2])
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
		}
		//第一种情况：root1的高度小于等于root2，直接将root2合并到root1上
		// （1）root1高度小于root2的高度，所以合并并不会导致高度增加
		//（2）如果root1的高度等于root2的高度，合并就会导致高度增加--->如果root2合并到root1，则root1高度会+1
		else
		{
			_ufs[root2] += _ufs[root1];
			_ufs[root1] = root2;
			if (_height[root1] == _height[root2])
				_height[root2]++;
		}

		return true;
	}

总代码

class UnionFindSet
{
public:
	UnionFindSet(size_t N)
	{
		_ufs.resize(N,-1);
		_height.resize(N, 1);
	}

	//查找它所属集合的根  带路径压缩的代码  循环版本
	int FindRoot(int index)
	{
		while (_ufs[index] >= 0)
		{
			_ufs[index] = _ufs[_ufs[index]];
			index = _ufs[index];
		}

		return index;
	}

	// 查找根节点（带路径压缩）   递归版本
	int FindRoot(int index)
	{
		if (_ufs[index] >=0)
		{
			_ufs[index] = FindRoot(_ufs[index]);  // 递归路径压缩
		}
		return _ufs[index];
	}

	//给两个下标，将两个标所属的集合合并成一个集合
	bool Union(int index1,int index2)
	{
		int root1 = FindRoot(index1);
		int root2 = FindRoot(index2);

		//属于同一个集合  直接返回
		if (root1 == root2) return false;

		//第一种情况：root1的高度大于root2，直接将root2合并到root1上，并且因为root1高度小于root2.合并并不会导致高度增加
		if (_height[root1] > _height[root2])
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
		}
		//第一种情况：root1的高度小于等于root2，直接将root2合并到root1上
		// （1）root1高度小于root2的高度，所以合并并不会导致高度增加
		//（2）如果root1的高度等于root2的高度，合并就会导致高度增加--->如果root2合并到root1，则root1高度会+1
		else
		{
			_ufs[root2] += _ufs[root1];
			_ufs[root1] = root2;
			if (_height[root1] == _height[root2])
				_height[root2]++;
		}

		return true;
	}

	// 检查两个元素是否属于同一集合
	bool isConnected(int x, int y)
	{
		return FindRoot(x) == FindRoot(y);
	}

	//统计集合的个数
	size_t Count()const
	{
		size_t count = 0;
		for (auto e : _ufs)
		{
			if (e < 0) ++count;
		}

		return count;
	}

	~UnionFindSet() {}
private:
	vector<int> _ufs;
	vector<int> _height;
};

并查集的应用

力扣：省份的数量

我的代码：

class Solution {
public:

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

        auto FindRoot = [&_ufs](int x)
        {
            while(_ufs[x]>=0)
            {
                x = _ufs[x];
            }

            return x;
        };
        for(int i = 0;i<n;++i)
        {
            for(int j = 0;j<n;++j)
            {
                if(isConnected[i][j]==1)
                {
                    int x = FindRoot(i);
                    int y = FindRoot(j);

                    if(x!=y)
                    {
                        _ufs[x]+=_ufs[y];
                        _ufs[y]=x;
                    }
                }
            }
        }

        int Count = 0;
        for(auto e:_ufs)
        {
            if(e<0) ++Count;
        }

        return Count;
    }
};

等式方程的可满足性

class Solution {
public:
    /*
    解题思路：
      1. 将所有"=="两端的字符合并到一个集合中
      2. 检测"!=" 两端的字符是否在同一个结合中，如果在不满足，如果不在满足
    */
    bool equationsPossible(vector<string>& eq) {
        vector<int> _ufs(26, -1);

        auto FindRoot = [&_ufs](int x) {
            while (_ufs[x] >= 0) {
                x = _ufs[x];
            }
            return x;
        };
        // 第一遍：把相等的合并
        for (auto str : eq) {
            if (str[1] == '=') {
                int rootx = FindRoot(str[0] - 'a');
                int rooty = FindRoot(str[3] - 'a');

                if (rootx != rooty) {
                    _ufs[rootx] += _ufs[rooty];
                    _ufs[rooty] = rootx;
                }
            }
        }
        // 第二遍：遍历，如果发现不相等的两个元素在一个集合，说明相悖，返回false
        for (auto str : eq) {
            if (str[1] == '!') {
                int rootx = FindRoot(str[0] - 'a');
                int rooty = FindRoot(str[3] - 'a');

                if (rootx == rooty)
                    return false;
            }
        }

        return true;
    }
};