赞
踩
在计算机科学中,并查集(英文:Disjoint-set data structure,直译为不数据结构交集)是一种数据结构,用于处理一些不交集(Disjoint sets,一系列没有重复元素的集合)的合并及查询问题。
举个简单的例子
一个组织里来个10个新人,它们的编号为从1~10,假设此时它们根据彼此的老家而互相亲近(即形成一个小团体),我们要将这10个人划分成不同的小团体,这样划分后形成的结果就是并查集。
接下来我们就来模拟这10个人的划分过程,首先我们可以将每个人的初始值设置为-1,当两个人都属于同一个小团体时,将其中一个人的-1加到另一个人身上,自己的值指向另一个人的下标, 此时另一个人就作为这一个小团体的根,这之后如果有新的人进入这个团体,将新人的-1加到根上,再让新人指向根的下标。这样操作后,所有人中只要自己的值<0,则表明自己是一个团队的根,绝对值表示团队人数,而团体中的其他人均指向这个根。
我们通过上面的模拟,我们可以发现并查集的主要操作主要是:合并,查找根,查看团队个数
我们使用C++实现这个数据结构有
- #pragma once
- #include <vector>
-
- using namespace std;
-
- class UnionFindSet
- {
- public:
- // 将并查集中的所有元素初始化为-1
- UnionFindSet(size_t n)
- :_ufs(n, -1)
- {}
-
- // 查找根
- int FindRoot(int x);
-
- // 合并
- void Union(int x1, int x2);
-
- // 查看集合个数
- size_t UnionCount(int x);
-
- private:
- vector<int> _ufs;
- };
- // 查找根
- int FindRoot(int x)
- {
- if (x >= _ufs.size())
- {
- throw invalid_argument("无效参数!");
- return -1;
- }
-
- int root = x;
- while (_ufs[root] >= 0) // 不为根就向上查找
- {
- root = _ufs[root];
- }
-
- return root;
- }
在合并时,有可能会出现两个团队互相合并的情况,此时我们只需要将其中一个团队的根的值加到另一个团队的根上,再让自己指向另一个团队的根即可,即
- // 合并
- void Union(int x1, int x2)
- {
- int root1 = FindRoot(x1);
- int root2 = FindRoot(x2);
-
- // 两个人属于不同的集合时,才需要进行合并
- if (root1 != root2)
- {
- _ufs[root1] += _ufs[root2];
- _ufs[root2] = root1;
- }
- }
- // 查看集合个数
- size_t UnionCount()
- {
- size_t ret = 0;
- for (auto& e : _ufs)
- {
- if (e < 0) ret++;
- }
-
- return ret;
- }
题目链接:LCR 116. 省份数量 - 力扣(LeetCode)
解析:分析题目,如果这道题使用并查集就没有那么难,整体思路就是如果两个城市相连就将他们合并为一个省份,最终返回省份个数即可
- class UnionFindSet
- {
- public:
- // 将并查集中的所有元素初始化为-1
- UnionFindSet(size_t n)
- :_ufs(n, -1)
- {}
-
- // 查找根
- int FindRoot(int x)
- {
- if (x >= _ufs.size())
- {
- throw invalid_argument("无效参数!");
- return -1;
- }
-
- int root = x;
- while (_ufs[root] >= 0) // 不为根就向上查找
- {
- root = _ufs[root];
- }
-
- return root;
- }
-
- // 合并
- void Union(int x1, int x2)
- {
- int root1 = FindRoot(x1);
- int root2 = FindRoot(x2);
-
- // 两个人属于不同的集合时,才需要进行合并
- if (root1 != root2)
- {
- _ufs[root1] += _ufs[root2];
- _ufs[root2] = root1;
- }
- }
-
- // 查看集合个数
- size_t UnionCount()
- {
- size_t ret = 0;
- for (auto& e : _ufs)
- {
- if (e < 0) ret++;
- }
-
- return ret;
- }
-
- private:
- vector<int> _ufs;
- };
-
- 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.UnionCount();
- }
- };
即
- class Solution
- {
- public:
- int findCircleNum(vector<vector<int>>& isConnected)
- {
- vector<int> ufs(isConnected.size(), -1);
- 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 ret = 0;
- for (auto& e : ufs)
- if (e < 0) ret++;
-
- return ret;
- }
- };
题目链接:990. 等式方程的可满足性 - 力扣(LeetCode)
解析:分析题目,我们可以使用并查集来解决这道题,即先将所有等式挑选出来,将它们中的元素合并,这之后再查看不等式,如果方程两边的元素同属于一个集合则证明相悖,解决如下
- 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& s : equations)
- {
- if (s[1] == '=')
- {
- int root1 = FindRoot(s[0] - 'a');
- int root2 = FindRoot(s[3] - 'a');
-
- if (root1 != root2)
- {
- ufs[root1] += ufs[root2];
- ufs[root2] = root1;
- }
- }
- }
-
- for (auto& s : equations)
- {
- if (s[1] == '!')
- {
- int root1 = FindRoot(s[0] - 'a');
- int root2 = FindRoot(s[3] - 'a');
-
- if (root1 == root2) return false;
- }
- }
-
- return true;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。