---

并查集

1、概念

并查集(Union-Find)是一种可以用来判断同属一个集合中相互关联的元素属于几个集合，也可以用来判断图结构中的两点是否是连通, 它也是一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。

2、根据人找编号 / 根据编号找人（简单介绍一下并查集）

（1）代码展示

// UnionFindSet.h
#pragma once

#include <vector>
#include <map>

template <class T>
class UnionFindSet
{
private:
	std::vector<T> _a;			// 编号找人
	std::map<T, int> _indexmap; // 人找编号的映射关系
public:
	UnionFindSet(const T* a, size_t n)
	{
		for (size_t i = 0; i < n; i++)
		{
			_a.push_back(a[i]);  // 将传进来的值存入到vector中
			_indexmap[a[i]] = i; // 映射关系
		}
	}
};

// photo.cpp
#include <iostream>
#include "UnionFindSet.h"

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

（2）调试结果

（3）优化1：小的往大的合并

（4）优化2：压缩路径

	// 找根
	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;
	}

3、并查集操作和演示题目

（1）并查集操作

i、思路

ii、总体代码

class UnionFindSet
{
private:
	std::vector<int> _ufs;
public:
	UnionFindSet(size_t n)
		: _ufs(n, -1)
	{}
	// 合并
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		// 俩根在一颗树上
		if (root1 == root2) return;

		// 更新
		_ufs[root1] += _ufs[root2]; // 前面的值+=后面的值
		_ufs[root2] = root1; // 更新后面的值为前面的值（双亲根）
	}
	// 找根
	int FindRoot(int x)
	{
		int parent = x;
		while (_ufs[parent] >= 0)
		{
			parent = _ufs[parent]; // 下标和值的关系
		}
		return parent;
	}
	// 判断是否是同一个树
	bool IsSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}
	// 算树的数量
	int Size()
	{
		int n = _ufs.size();
		int size = 0;
		for (int i = 0; i < n; i++)
		{
			if (_ufs[i] < 0)
			{
				size++;
			}
		}
		return size;
	}
};

（2）演示题目：省份数量

i、做法一：自己写一个并查集

leetcode题目链接跳转

class UnionFindSet
{
private:
	std::vector<int> _ufs;
public:
	UnionFindSet(size_t n)
		: _ufs(n, -1)
	{}
	// 合并
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		// 俩根在一颗树上
		if (root1 == root2) return;

		// 更新
		_ufs[root1] += _ufs[root2]; // 前面的值+=后面的值
		_ufs[root2] = root1; // 更新后面的值为前面的值（双亲根）
	}
	// 找根
	int FindRoot(int x)
	{
		int parent = x;
		while (_ufs[parent] >= 0)
		{
			parent = _ufs[parent]; // 下标和值的关系
		}
		return parent;
	}
	// 判断是否是同一个树
	bool IsSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}
	// 算树的数量
	int Size()
	{
		int n = _ufs.size();
		int size = 0;
		for (int i = 0; i < n; i++)
		{
			if (_ufs[i] < 0)
			{
				size++;
			}
		}
		return size;
	}
};
class Solution 
{
public:
    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        UnionFindSet ufs(isConnected.size());
        for (int i = 0; i < isConnected.size(); i++)
        {
            for (int j = 0; j < isConnected[i].size(); j++)
            {
                if (isConnected[i][j] == 1)
                {
                    ufs.Union(i, j);
                }
            }
        }
        return ufs.Size();
    }
};

ii、做法二：手动版本

class Solution 
{
public:
    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        vector<int> ufs(isConnected.size(), -1);

		// lambda表达式
        auto FindRoot = [&ufs](int x) 
        {
            while (ufs[x] >= 0) x = ufs[x];
            return x;
        };
        for (int i = 0; i < isConnected.size(); i++)
        {
            for (int j = 0; j < isConnected[i].size(); 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 n = 0;
        for (auto e : ufs)
        {
            if (e < 0)
                n++;
        }
        return n;
    }
};

（3）演示题目：等式方程可满足性

leetcode题目链接跳转

进行两次遍历，第一次遍历假如说是中间是等号的情况下的话，就将俩字母都放到同一个集合中，第二次遍历假如说是中间是不等号的情况下的话，就判断俩字母是否是在同一个集合中，在的话就返回false，不在的话就返回true。

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

		// lambda表达式
        auto FindRoot = [&ufs](int x) 
        {
            while (ufs[x] >= 0) x = ufs[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)
                {
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            }
        }
        // 第二遍遍历，遇到相同的俩字母在一个集合中就返回false
        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;
    }
};