数据结构之并查集

并查集原理

首先需要明确, 并查集是一个森林

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

举例: 

有10个人来自不同的学校, 起先互不相识, 每个学生都是一个独立的小团体, 现给这些学生进行编号：{0, 1, 2, 3,4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体, 数组中的数字的绝对值代表: 该小集体中具有成员的个数

现在学生们按照家乡划分成了三组: 江苏学生小分队s1={0,6,7,8}，山东学生小分队s2={1,4,9}, 浙江学生小分队s3={2,3,5}就相互认识了, 10个人形成了三个小团体. 假定以坐标小的0,1,2担任队长:

 一趟旅行之后, 每个小分队成员就互相熟悉, 形成了一个朋友圈, 3个小团体合并成了一个大团体:

仔细观察数组中的下标, 可以得出:

1. 数组中一个位置的值如果为负数, 那它就是树的根, 负数的绝对值就是这棵树的数据的个数.
2. 数组中一个位置的值如果为非负数, 代表该位置值双亲的下标 

通过以上例子可知，并查集一般可以解决以下问题:

1. 查找元素属于哪个集合
        沿着数组表示的树形关系, 往上一直找到根(即: 树中中元素为负数的位置)
2. 查看两个元素是否属于同一个集合
        沿着数组表示的树形关系往上一直找到树的根, 如果根相同表明在同一个集合, 否则不在
3. 将两个集合归并成一个集合
        将两个集合中的元素合并
        将一个集合名称改成另一个集合的名称
4. 集合的个数
        遍历数组, 数组中元素为负数的个数即为集合的个数。 

---

并查集实现 

主要实现三个接口, 其中FindRoot接口是Union接口的子函数.

1. 构造函数将数组全部初始化为-1

2. Union是将两个位置所在的并查集合并, 要想合并要先找它们的根看是否在一个并查集, 是的话就不需要合并, 所以先实现FindRoot. 合并注意一个细节, 可以把集合元素少的向集合元素多的去合并, 因为被合并的那个集合所有节点的深度都会+1, 所以让更少的元素集合合并到更多的元素集合可以提高FindRoot的效率.

3. FindRoot 一直查询位置对应的值是不是负值即可

4. SetSize查询共有几个并查集, 统计数组中负数的个数即可.

在查询的过程中我们还可以顺便实现压缩路径的操作:

在不断的Union之后, 可能有的节点的层数会很深, FindRoot的时候需要向上查找很多次, 所以在每一次查找完Root之后, 通过比对 当前位置的直接根 是否等于查找之后的Root, 如果不是说明该节点的层次大于2层, 就可以合并了, 把该节点的下标修改为之前查找到的Root即可, 而且可以顺着该节点依次向上遍历, 可以把路径上所有高度大于2的结点全部合并到Root之下.

#include <iostream>
#include <vector>
 
class UnionFindSet
{
public:
	UnionFindSet(int n)
		:ufs(n,-1)
	{}
 
	void Union(int i, int j)
	{
		int rooti = FindRoot(i);
		int rootj = FindRoot(j);
		if (rooti == rootj)
			return;
		else
		{
            //保持rooti为集合内元素多的根, 注意ufs[rooti]内是负值, 数值大的元素反而少
            if (ufs[rooti] > ufs[rootj])
	            std::swap(rooti, rootj);
			ufs[rooti] += ufs[rootj];
			ufs[rootj] = rooti;
		}
	}
 
	int FindRoot(int x)
	{
		int root = x;
		while (ufs[root] >= 0)
		{
			root = ufs[root];
		}
		//查找途中顺便压缩路径
		while(ufs[x] >=0)
		{
			int lastparent = ufs[x];
			ufs[x] = root;
			x = lastparent;
		}
		return root;
	}
 
	int SetSize()
	{
		int ret = 0;
		int n = ufs.size();
		for (int i = 0; i < n; i++)
		{
			if (ufs[i] < 0)
				ret++;
		}
		return ret;
	}
 
    //判断两个节点是否在同一个并查集, 克鲁斯卡尔算法会用到
    bool InSet(size_t a, size_t b)
    {
	    size_t root1 = FindRoot(a);
	    size_t root2 = FindRoot(b);
	    return root1 == root2;
    }
private:
	std::vector<int> ufs;
};

---

并查集解决例题

 省份数量

直接把并查集拷贝过来, isConnected[i][j]==1就Union(i,j), 最后返回并查集的个数即可, 只需要调用并查集的两个接口:

class UnionFindSet
{
public:
	UnionFindSet(int n)
		:ufs(n,-1)
	{}
 
	void Union(int i, int j)
	{
		int rooti = FindRoot(i);
		int rootj = FindRoot(j);
		if (rooti == rootj)
			return;
		else
		{
			if (rooti > rootj)
				std::swap(rooti, rootj);//保持rooti为小坐标
			ufs[rooti] += ufs[rootj];
			ufs[rootj] = rooti;
		}
	}
 
	int FindRoot(int x)
	{
		int parent = x;
		while (ufs[parent] >= 0)
		{
			parent = ufs[parent];
		}
		//查找途中顺便压缩路径
		if (x >= 0 && parent != ufs[x])
		{
			while (x != parent)
			{
				int lastparent = ufs[x];
				ufs[x] = parent;
				x = lastparent;
			}
		}
		return parent;
	}
 
	int SetSize()
	{
		int ret = 0;
		int n = ufs.size();
		for (int i = 0; i < n; i++)
		{
			if (ufs[i] < 0)
				ret++;
		}
		return ret;
	}
private:
	std::vector<int> ufs;
};
 
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        int x = isConnected.size();
        int y = isConnected[0].size();
        UnionFindSet s(x);
        for(int i = 0; i < x; i++)
        {
            for(int j = 0; j < y; j++)
            {
                if(i == j)
                    continue;
                if(isConnected[i][j] == 1)
                {
                    s.Union(i,j);
                }
            }
        }
        return s.SetSize();
    }
};

用并查集的思想也可以, 只不过把并查集的关键代码重写一遍: 

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        int x = isConnected.size();
        int y = isConnected[0].size();
        vector<int> ufs(x,-1);
 
        auto FindRoot = [&ufs](int x)
        {
            int parent = x;
            while(ufs[parent] >= 0)
            {
                parent = ufs[parent];
            }
            return parent;
        };
        for(int i = 0; i < x; i++)
        {
            for(int j = 0; j < y; 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 ret  =0;
        for(auto e:ufs)
        {
            if(e <0)
                ret++;
        }
        return ret;
    }
};

 等式方程的可满足性

 将相等的元素合并到一个并查集, 最后查询不相等的元素的是不是在一个并查集下即可:

class Solution {
public:
    bool equationsPossible(vector<string>& equations) 
    {
        vector<int> ufs(26,-1);
        auto FindRoot = [&ufs](int x)
        {
            while(ufs[x] >=0)
            {
                x = ufs[x];
            }
            return x;
        };
 
        for(auto& equation: equations)
        {
            if(equation[1] == '=') 
            {
                int root1 = FindRoot(equation[0]-'a');
                int root2 = FindRoot(equation[3]-'a');
                if(root1 != root2)
                {
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            }
        }
 
        for(auto& equation: equations)
        {
            if(equation[1] == '!')
            {
                int root1 = FindRoot(equation[0]-'a');
                int root2 = FindRoot(equation[3]-'a');
                if(root1 == root2)
                    return false;
            }
        }
        return true;
    }
};

---