关键词：
2018-05-01 15:13:08
并查集是一个时空复杂度非常优越的数据结构，并且通过优化后其复杂度为<O(1)，O(n)>。
并查集的优化主要有两个方面：
- 路径压缩
- 按rank来合并
路径压缩：
按rank合并：
public class UnionFindSet
private int[] parent;
private int[] rank;
public UnionFindSet(int n)
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 0; i < n + 1; i++)
parent[i] = i;
rank[i] = 1;
public int find(int i)
if (parent[i] != i)
parent[i] = find(parent[i]);
return parent[i];
public boolean union(int i, int j)
int pi = find(i);
int pj = find(j);
if (pi == pj) return false;
if (rank[pi] > rank[pj])
parent[pj] = pi;
else if (rank[pi] < rank[pj])
parent[pi] = pj;
else
parent[pj] = pi;
rank[pi]++;
return true;
-
684. Redundant Connection
问题描述：
问题求解：
树形下的无向图判断环路问题，图的描述方式是采用边集。
并查集本身就是树形结构，而树是一个无向图，具体来说，树是一个无环的连通图，所以本题可以直接使用并查集来进行求解。
public int[] findRedundantConnection(int[][] edges)
UnionFindSet ufs = new UnionFindSet(edges.length + 1);
int[] res = new int[2];
for (int[] pair : edges)
if (!ufs.union(pair[0], pair[1]))
res[0] = Math.min(pair[0], pair[1]);
res[1] = Math.max(pair[0], pair[1]);
break;
return res;
2019.04.21
public int[] findRedundantConnection(int[][] edges)
int n = edges.length;
int[] parent = new int[n + 1];
for (int i = 1; i <= n; i++) parent[i] = i;
for (int[] edge : edges)
if (!union(parent, edge[0], edge[1]))
Arrays.sort(edge);
return edge;
return null;
private int find(int[] parent, int i)
if (parent[i] != i)
parent[i] = find(parent, parent[i]);
return parent[i];
private boolean union(int[] parent, int i, int j)
int pi = find(parent, i);
int pj = find(parent, j);
if (pi == pj) return false;
parent[pj] = pi;
return true;
-
547. Friend Circles
问题描述：
问题求解：
class Solution
public int findCircleNum(int[][] M)
UnionFindSet ufs = new UnionFindSet(M.length);
int res = 0;
for (int i = 0; i < M.length; i++)
for (int j = 0; j < i; j++)
if (M[i][j] == 1)
ufs.union(i, j);
for (int i = 0; i < ufs.parent.length; i++)
if (ufs.parent[i] == i) res++;
return res;
class UnionFindSet
public int[] parent;
private int[] rank;
public UnionFindSet(int n)
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++)
parent[i] = i;
rank[i] = 1;
public int find(int i)
if (parent[i] != i)
parent[i] = find(parent[i]);
return parent[i];
public boolean union(int i, int j)
int pi = find(i);
int pj = find(j);
if (pi == pj) return false;
if (rank[pi] > rank[pj])
parent[pj] = pi;
else if (rank[pi] < rank[pj])
parent[pi] = pj;
else
parent[pj] = pi;
rank[pi]++;
return true;
-
765. Couples Holding Hands
问题描述：
问题求解：
这里有一个O(n)的做法， 一次考虑两个凳子，假设他们不为夫妇，为了让这两个位置坐的恰好是一对夫妇，那么我们就需要调整其中一个人的位置，如此调整直到所有的夫妇相邻，交换的次数就是答案。下面给出证明。
将给定的row抽象成一个n个顶点的无向图（可能包含重边），例如：
(_ _) (_ _) ... (_ _)
(v1 ) (v2 ) ... (vn )
vi和vj之间存在边当且仅当vi和vj中存在一对夫妇，例如vi = （0，2），vj = （1， 4）存在一对夫妇（0， 1），而vi = （0， 2），vj = （1， 3）之间则存在两对夫妇（0， 1）（2， 3），此vi和vj存在重边。
考虑row数组形成的无向图，可以肯定要么是孤立的单个节点，要么是多个孤立的圈，例如row = [0, 1]是一个孤立的点、row = [0, 2, 1, 3]则包含一个圈v1, v2、row = [0, 3, 4, 1, 2, 5, 6, 8, 7, 9]，包含两个孤立的圈v1, v2, v3和v4, v5。
对于一个圈来说，假设他有n个节点，那么至少需要n-1次交换即可让每个夫妇相邻。有了这个结论，假定row数组有n个点，m个孤立的圈，那么至少需要n-m次交换即可。
public int minSwapsCouples(int[] row)
int n = row.length / 2;
int[] parent = new int[n];
int cnt = n;
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 0; i < n * 2; i += 2)
if (union(parent, row[i] / 2, row[i + 1] / 2)) cnt--;
return n - cnt;
private int find(int[] parent, int i)
if (parent[i] != i)
parent[i] = find(parent, parent[i]);
return parent[i];
private boolean union(int[] parent, int i, int j)
int pi = find(parent, i);
int pj = find(parent, j);
if (pi == pj) return false;
parent[pj] = pi;
return true;
- 947. Most Stones Removed with Same Row or Column
问题描述：
问题求解：
这个问题可以转化为求图中连通数的问题，也就是经典的陆地数量问题。对于x | y相等的两个石头我们需要建立他们之间的联系。
经典的连通子树问题可以使用dfs进行求解，从dfs的算法过程我们可以看到其实是一棵以起始点为root的树，因此，在这次dfs中我们总可以从叶子节点开始选取，知道最后只剩下root节点。
最终的答案就是所有的stones的数目 - 连通块的数目。
这里并不打算使用dfs来进行求解，将使用ufs来进行求解。
使用并查集并不需要那么形式化的专门使用一个类来进行表征，这就是一个简单的数据结构，只需要在使用前进行定义就好了，另外，由于parent的数目范围不确定，所以在很多时候使用数组并不是一个合适的选择，使用hash表更能方便我们解决问题，本题就是使用hash表来进行的并查集的实现。
public int removeStones(int[][] stones)
Map<Integer, Integer> parent = new HashMap<>();
int n = stones.length;
for (int[] stone : stones)
union(parent, stone[0], stone[1] + 10000);
int cnt = 0;
for (int key : parent.keySet())
if (parent.get(key) == key) cnt++;
return n - cnt;
private int find(Map<Integer, Integer> parent, int i)
if (!parent.containsKey(i)) parent.put(i, i);
if (parent.get(i) != i)
parent.put(i, find(parent, parent.get(i)));
return parent.get(i);
private boolean union(Map<Integer, Integer> parent, int i, int j)
int pi = find(parent, i);
int pj = find(parent, j);
if (pi == pj) return false;
parent.put(pj, pi);
return true;
- 959. Regions Cut By Slashes
问题描述：
问题求解：
主要问题就是怎么将字符串的输入进行转化，这里采用的转化方式是将每个cell看成4个区域，0-3。根据不同的情况可以将各个区域进行合并，这样本题就又变成了并查集问题。
int n;
public int regionsBySlashes(String[] grid)
n = grid.length;
int[] parent = new int[n * n * 4];
for (int i = 0; i < parent.length; i++) parent[i] = i;
int size = n * n * 4;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i > 0 && union(parent, getIdx(i - 1, j, 2), getIdx(i, j, 0))) size--;
if (j > 0 && union(parent, getIdx(i, j - 1, 1), getIdx(i, j, 3))) size--;
if (grid[i].charAt(j) != \'/\')
if (union(parent, getIdx(i, j, 0), getIdx(i, j, 1))) size--;
if (union(parent, getIdx(i, j, 2), getIdx(i, j, 3))) size--;
if (grid[i].charAt(j) != \'\\\\\')
if (union(parent, getIdx(i, j, 0), getIdx(i, j, 3))) size--;
if (union(parent, getIdx(i, j, 1), getIdx(i, j, 2))) size--;
return size;
private int find(int[] parent, int i)
if (parent[i] != i)
parent[i] = find(parent, parent[i]);
return parent[i];
private boolean union(int[] parent, int i, int j)
int pi = find(parent, i);
int pj = find(parent, j);
if (pi == pj) return false;
parent[pj] = pi;
return true;
private int getIdx(int i, int j, int num)
return i * n * 4 + j * 4 + num;
并查集的应用
定义 并查集是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题。常常在使用中以森林来表示。应用 若某个朋友圈过于庞大，要判断两个人是否是在一个朋友圈，确实还很不容易，给出某个... 查看详情
并查集的应用
定义 并查集是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题。常常在使用中以森林来表示。应用 若某个朋友圈过于庞大，要判断两个人是否是在一个朋友圈，确实还很不容易，给出某个... 查看详情
数据结构--并查集的原理及实现(代码片段)
一，并查集的介绍 并查集（Union/Find）从名字可以看出，主要涉及两种基本操作:合并和查找。这说明，初始时并查集中的元素是不相交的，经过一系列的基本操作(Union)，最终合并成一个大的集合。而在某次合并之后，有一种... 查看详情
并查集的原理及实现(代码片段)
一、定义 并查集是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题。二、代码实现 在并查集结构中，用一个pre[]数组来存储当前结点的父亲结点，有两个函数，found()函数用来寻找根结点，... 查看详情
关于并查集的一切全在这里了(代码片段)
文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情
poj2236（并查集的应用）(代码片段)
WirelessNetworkTimeLimit: 10000MS MemoryLimit: 65536KTotalSubmissions: 35832 Accepted: 14863DescriptionAnearthquaketakesplaceinSoutheastAsia.TheACM(AsiaCooperatedMedicalt 查看详情
❤️数据结构入门❤️（2-5）-并查集
文章目录一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、并查集的删除3、并查集的修改4、并查集的查找四、并查集的刷题实战一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、... 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集... 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归(深度过深有栈溢出的风险)并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每... 查看详情
并查集的基础
...ss/article/details/7724401/史上最容易理解的解答！没有之一。并查集能实现的功能：判断是否成环，计算共有多少个非连通图。。。待日后填坑在最小生成树中应用并查集最简代码！intf(intx){returnx==pre[x]?x:pre[x]=f(pre[x]);} voidmix(inta,... 查看详情
并查集的简介
最近做题用到了并查集索性就把自己所掌握的相关知识总结一下。 并查集(union-findsets),CLRS上称为disjoint-set,是一组不相交的动态集合S1,S2,....Sk。它能够实现较快的合并和判断元素所在集合的操作，应用比较广泛，如其求... 查看详情
数据结构——并查集的详细解析和实现(代码片段)
...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情
数据结构——并查集的详细解析和实现(代码片段)
...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情
并查集入门
并查集的基础概念及实现部分内容引用自wikipedia.org并查集(Union-FindSets)是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题，定义了两个用于此数据结构的操作：Find：确定元素属于哪一个子集。它可以被用来确定... 查看详情
树--12---并查集(代码片段)
文章目录并查集并查集是一种树型的数据结构并查集结构1.并查集的实现API设计UF(intN)构造方法实现union(intp,intq)合并方法实现代码：测试：案例1:计算机网诺连接2.UF_Tree算法优化eleAndGourp数组API设计find(intp)查询方法实现unio... 查看详情
并查集介绍及实现以及相关例题(代码片段)
并查集的原理和使用背景在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某... 查看详情
并查集详解(代码片段)
目录并查集（Union-Find）初始化的两种方法：并集的三种方法：查集的两种方法：“并“、”查”的基本方法与优化源代码并查集（Union-Find）常用来解决动态连通性问题。曾有外国网友在StackExchange上发起过投票，选出世界十大有... 查看详情
算法笔记之并查集(代码片段)
并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。常常在使用中以森林来表示。一、并查集的定义并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题... 查看详情