并查集-摩杜云开发者社区

并查集的原理

来自百度百科

并查集，在一些有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;
    }
};