并查集（1） |
您所在的位置：网站首页 › 连通集的并连通吗 › 并查集（1） |
并查集（1）
|
并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作： 合并（Union）：把两个不相交的集合合并为一个集合。查询（Find）：查询两个元素是否在同一个集合中。当然，图论相关的问题，可以用并查集解决时，一般也可以用BFS或DFS来解决，此处不再展开，BFS和DFS相关算法可见此篇 文章。 基本概念 并查集是一种数据结构并查集这三个字，一个字代表一个意思： 并（Union），代表合并查（Find），代表查找集（Set），代表这是一个以字典（数组也可以）为基础的数据结构，它的基本功能是合并集合中的元素，查找集合中的元素 并查集的典型应用是有关连通分量的问题并查集解决单个问题（添加，合并，查找）的时间复杂度都是O(1) 。因此，并查集可以应用到在线算法中并查集跟树有些类似，只不过她跟树是相反的。在树这个数据结构里面，每个节点会记录它的子节点。在并查集里，每个节点会记录它的父节点。 并查集的引入并查集的重要思想在于，用集合中的一个元素代表集合。我曾看过一个有趣的比喻，把集合比喻成帮派，而代表元素则是帮主。接下来我们利用这个比喻，看看并查集是如何运作的。 现在1号和3号比武，假设1号赢了（这里具体谁赢暂时不重要），那么3号就认1号作帮主（合并1号和3号所在的集合，1号为代表元素）。 合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。本文末尾会给出一个更合理的比较方法。 并查集实现的优化 1.路径压缩最简单的并查集效率是比较低的。例如，来看下面这个场景：
怎么解决呢？我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步，像这样： 以上代码常常简写成一行： int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); }注意赋值运算符=的优先级没有三元运算符?:高，这里要加括号。 路径压缩优化后，并查集的时间复杂度已经比较低了，绝大多数不相交集合的合并查询问题都能够解决。然而，对于某些时间卡得很紧的题目，我们还可以进一步优化。 2.按秩合并有些人可能有一个误解，以为路径压缩优化后，并查集始终都是一个菊花图（只有两层的树的俗称）。但其实，由于路径压缩只在查询时进行，也只压缩一条路径，所以并查集最终的结构仍然可能是比较复杂的。例如，现在我们有一棵较复杂的树需要与一个单元素的集合合并： 当然是后者。因为如果把7的父节点设为8，会使树的深度（树中最长链的长度）加深，原来的树中每个元素到根节点的距离都变长了，之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩，但路径压缩也是会消耗时间的。而把8的父节点设为7，则不会有这个问题，因为它没有影响到不相关的节点。 我们用一个数组rank[ ] 记录 每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。 一开始，把所有元素的rank（秩）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。路径压缩和按秩合并如果一起使用，时间复杂度接近O(n) ，但是很可能会破坏rank的准确性。 值得注意的是，按秩合并会带来额外的空间复杂度，可能被一些卡空间的毒瘤题卡掉。 初始化（按秩合并） inline void init(int n) { for (int i = 1; i int x = find(i), y = find(j); //先找到两个根节点 if (rank[x] fa.resize(n); rank.resize(n);//容量个数别忘了初始化，不然下面不好直接赋值 for(int i = 0; i for(int i = 0; i return fa[x] == x ? x : (fa[x] = find(fa[x])); } ====================================================== //并（按秩合并） void merge(int x, int y){ int fx = find(x), fy = find(y);//先找各自根节点 if(rank[fx] fa[fy] = fx; } //更新秩的大小 if(rank[fx] == rank[fy] && fx != fy){ rank[fy]++;//如果深度相同且根节点不同，则新的根节点的深度+1 } } }; 例题实战 1. leetcode1202. 交换字符串中的元素给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。 你可以 任意多次交换 在 pairs 中任意一对索引处的字符。 返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。 class DisjoinSetUnion{ private: vector father, rank;//定义一个连通图（并查集），每个节点的秩（按秩合并） int n; public: DisjoinSetUnion(int num){ n = num; rank.resize(n, 1);//每个节点秩初始化为1 father.resize(n); //初始化连通图（并查集） for(int i = 0; i return father[x] == x ? x : (father[x] = find(father[x]));//路径压缩 } //并：合并到一个图中，即拥有共同祖宗 void unionSet(int x, int y){ int fx = find(x), fy = find(y);//找到两个根（祖宗）节点 //秩小的树 连到 秩大的树上（秩不会增加，只有秩相等时相连，秩+1） if(rank[fx] father[fy] = fx; } //更新秩 if(rank[fx] == rank[fy] && fx != fy){ rank[fy]++;//如果深度相同且根节点不同，则新的根节点的深度+1 } } }; class Solution { public: string smallestStringWithSwaps(string s, vector& pairs) { //初始化连通图（并查集） DisjoinSetUnion ufs(s.length()); //合并 for(auto &iter : pairs){ ufs.unionSet(iter[0], iter[1]); } //哈希表存储 下标：可换至该下标所有元素 unordered_map mp; for(int i = 0; i sort(vec.begin(), vec.end(), greater());//按从大到小排序 } for(int i = 0; i public: vector fa, rank; //构造并查集 UnionFindSet(int n){ for(int i = 0; i return fa[x] == x ? x : (fa[x] = find(fa[x])); } //按秩合并 void merge(int x, int y){ int fa_x = find(x), fa_y = find(y); if(rank[fa_x] fa[fa_y] = fa_x; } //更新秩 if(rank[fa_x] == rank[fa_y] && fa_x != fa_y){ rank[fa_y]++; } } }; class Solution { public: int findCircleNum(vector& isConnected) { //并查集寻找连通域 int n = isConnected.size(); //初始化并查集 UnionFindSet ufs(n); //根据题目条件合并 for(int i = 0; i if(isConnected[i][j] == 1){ ufs.merge(i, j); } } } //找到各个连通域数量即为答案 int cnt = 0; for(int i = 0; i cnt++; } } return cnt; } }; 3.（洛谷P1551）亲戚问题题目背景 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 题目描述 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。 输入格式 第一行：三个整数n,m,p，（n fa[i] = i; rank[i] = 1; } } int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); } inline void merge(int i, int j) { int x = find(i), y = find(j); if (rank[x] scanf("%d%d", &x, &y); merge(x, y); } for (int i = 0; i private: vector fa, rank; public: //初始化构造并查集 UnionFindSet(int n){ fa.resize(n+1); rank.resize(n+1); for(int i = 1; i return fa[x] == x ? x : (fa[x] = find(fa[x])); } //并 bool merge(int x, int y){ int fx = find(x), fy = find(y); if(fx == fy) return false;//若传进的两个顶点都已联通过了（根相同）则代表冗余成环 if(rank[fx] fa[fy] = fx; } //更新秩 if(fx != fy && rank[fx] == rank[fy]){ rank[fy]++; } return true; } }; class Solution { public: vector findRedundantConnection(vector& edges) { int n = edges.size(); vector ans; UnionFindSet ufs(n); for(auto &vec : edges){ if(!ufs.merge(vec[0], vec[1])){ ans.push_back(vec[0]); ans.push_back(vec[1]); } } return ans; } }; 5. leetcode947. 移除最多的同行或同列石头 n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。 如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。 给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。 经过仔细分析可以发现：这是一个图论的题，只要两个点处于同一行或者同一列，那么就可以删除其中一个点。 我们可以通过并查集合并同行同列的点，一个并查集只保留一个点即可。 即 最终移除个数 = 石头数量 - 并查集数量 class UnionFindSet{ public: vector fa, rank; //构造函数,初始化并查集 UnionFindSet(int n) : fa(vector(n)), rank(vector(n)) { for(int i = 0; i return fa[x] == x ? x : (fa[x] = find(fa[x])); } //merge 把同行或同列的合并 void merge(int x, int y){ int fax = find(x), fay = find(y); if(rank[fax] fa[fay] = fax; } //更新秩 if(fax != fay && rank[fax] == rank[fay]) rank[fay]++; } }; //思路：将同行同列的石头合在一个并查集中，每个并查集保留一个石头即可，即 最终移除个数 = 石头数量 - 并查集数量 class Solution { public: int removeStones(vector& stones) { int n = stones.size(), cnt = 0; UnionFindSet ufs(n); //对于每个石头(x,y):x或y坐标相同的代表在同行或同列，都要合并 for(int i = 0; i if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]){ ufs.merge(i, j); } } } //找合并完成后共有几个并查集 for(int i = 0; i public: unordered_map fa, rank;//优化：用hash表记录 行 与 列，之前用vector是以单个石头为基本单位,现在以行列为基本单位 int cnt = 0; //find,并初始化并查集和秩 int find(int x){ //初始化 if(fa.find(x) == fa.end()){ fa[x] = x; rank[x] = 1; cnt++;//统计行列值总个数（不重复） } return fa[x] == x ? x : (fa[x] = find(fa[x])); } //merge 把同行或同列的合并 void merge(int x, int y){ int fax = find(x), fay = find(y); if(fax != fay) cnt--;//找到属于同一个并查集的就减一，剩下的即为并查集个数 if(rank[fax] fa[fay] = fax; } //更新秩 if(fax != fay && rank[fax] == rank[fay]) rank[fay]++; } //返回并查集个数 int ufsNum(){ return cnt; } }; //思路：将同行同列的石头合在一个并查集中，每个并查集保留一个石头即可，即 最终移除个数 = 石头数量 - 并查集数量 class Solution { public: int removeStones(vector& stones) { int n = stones.size(); UnionFindSet ufs; //对每个石头的行列合并，防止行列数字相同冲突，加上10001(0 |
最开始，所有大侠各自为战。他们各自的帮主自然就是自己。（对于只有一个元素的集合，代表元素自然是唯一的那个元素）
现在2号想和3号比武（合并3号和2号所在的集合），但3号表示，别跟我打，让我帮主来收拾你（合并代表元素）。不妨设这次又是1号赢了，那么2号也认1号做帮主。 
现在我们假设4、5、6号也进行了一番帮派合并，江湖局势变成下面这样： 
现在假设2号想与6号比，跟刚刚说的一样，喊帮主1号和4号出来打一架（帮主真辛苦啊）。1号胜利后，4号认1号为帮主，当然他的手下也都是跟着投降了。 
好了，比喻结束了。如果你有一点图论基础，相信你已经觉察到，这是一个树状的结构，要寻找集合的代表元素，只需要一层一层往上访问父节点（图中箭头所指的圆），直达树的根节点（图中橙色的圆）即可。根节点的父节点是它自己。我们可以直接把它画成一棵树： 
用这种方法，我们可以写出最简单版本的并查集代码。
现在我们要merge(2,3)，于是从2找到1，fa[1]=3，于是变成了这样： 
然后我们又找来一个元素4，并需要执行merge(2,4)：
从2找到1，再找到3，然后fa[3]=4，于是变成了这样： 
大家应该有感觉了，这样可能会形成一条长长的链，随着链越来越长，我们想要从底部找到根节点会变得越来越难。
其实这说来也很好实现。只要我们在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，我们就可以省很多事。这用递归的写法很容易实现：
假如这时我们要merge(7,8)，如果我们可以选择的话，是把7的父节点设为8好，还是把8的父节点设为7好呢？
这启发我们：我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。【本文地址】
今日新闻 |
推荐新闻 |