什么平台可以推广,佛山百度seo排名,网站下载软件怎么安装,网站建设开票属于什么服务想要精通算法和SQL的成长之路 - 并查集的运用 前言一. 并查集的使用和模板1.1 初始化1.2 find 查找函数1.3 union 合并集合1.4 connected 判断相连性1.5 完整代码 二. 运用案例 - 省份数量 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 并查集的使用和模板
先说一下并查集… 想要精通算法和SQL的成长之路 - 并查集的运用 前言一. 并查集的使用和模板1.1 初始化1.2 find 查找函数1.3 union 合并集合1.4 connected 判断相连性1.5 完整代码 二. 运用案例 - 省份数量 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 并查集的使用和模板
先说一下并查集的相关知识点
含义并查集用于维护一组不相交的集合支持合并两个集合和查询某个元素所属的集合。用途解决图论、连通性问题和动态连通性等问题。
通俗一点可以使用并查集的算法题目有哪些特征
需要将n个不同的元素划分为不相交的集合。开始的时候每个元素自行成为一个集合然后需要根据一定的顺序进行 合并。同时还需要 查询 某个元素是否属于哪个集合。
因此并查集的基本操作可以包含两个
合并将两个不相交的集合合并成一个集合。将其中一个集合的根节点连接到另一个集合的根节点上查找根据某个元素寻找到它所在集合的根节点。
1.1 初始化
首先我们考虑下并查集里面需要有哪些数据结构
需要一个parent[]数组用来存储每个元素对应的根节点。再来一个rank[]数组代表以每个元素作为根节点其所在集合的大小。即代表某个集合的深度。再来一个sum字段代表当前的集合个数。
public class UnionFind {/*** 表示节点i的父节点*/private int[] parent;/*** 表示以节点i为根节点的子树的深度初始时每个节点的深度都为0*/private int[] rank;private int sum;public UnionFind(int n) {parent new int[n];rank new int[n];// 初始时每个节点的父节点都是它自己for (int i 0; i n; i) {parent[i] i;}sum n;}
}1.2 find 查找函数
特征
入参元素x。要做的事情不断地向上递归寻找这个x的根节点。递归终止条件找到根节点。根节点和元素本身一致
代码如下
public int find(int x) {while (x ! parent[x]) {x parent[x];}return x;
}1.3 union 合并集合
特征
入参元素x和y。要做的事情分别找到这两个元素的根节点rootX和rootY。如果俩元素的根节点是同一个说明他们在一个集合当中不需要任何操作。倘若两个元素的根节点不一样根据两个集合的深度来判断。将深度小的那个集合合并到深度大的集合中。同时更新对应的根节点和深度大小。
除此之外我们还可以写一个简单的函数用来判断两个元素是否处于同一个集合当中或者是是否相连
public void union(int x, int y) {int rootX find(x);int rootY find(y);// 如果两个元素的根节点一致不需要合并if (rootX rootY) {return;}// 如果根节点 rootX 的深度 rootY。if (rank[rootX] rank[rootY]) {// 那么将以rootY作为根节点的集合加入到rootX对应的集合当中rank[rootX] rank[rootY];// 同时改变rootY的根节点指向rootX。parent[rootY] rootX;} else {// 反之rank[rootY] rank[rootX];parent[rootX] rootY;}
}1.4 connected 判断相连性
/*** 判断两个节点是否在同一个集合中
*/
public boolean connected(int x, int y) {return find(x) find(y);
}1.5 完整代码
/*** author Zong0915* date 2023/10/4 下午2:52*/
public class UnionFind {/*** 表示节点i的父节点*/private int[] parent;/*** 表示以节点i为根节点的子树的深度初始时每个节点的深度都为0*/private int[] rank;private int sum;public UnionFind(int n) {parent new int[n];rank new int[n];// 初始时每个节点的父节点都是它自己for (int i 0; i n; i) {parent[i] i;}sum n;}public int find(int x) {while (x ! parent[x]) {x parent[x];}return x;}public void union(int x, int y) {int rootX find(x);int rootY find(y);// 如果两个元素的根节点一致不需要合并if (rootX rootY) {return;}// 如果根节点 rootX 的深度 rootY。if (rank[rootX] rank[rootY]) {// 那么将以rootY作为根节点的集合加入到rootX对应的集合当中rank[rootX] rank[rootY];// 同时改变rootY的根节点指向rootX。parent[rootY] rootX;} else {// 反之rank[rootY] rank[rootX];parent[rootX] rootY;}}/*** 判断两个节点是否在同一个集合中*/public boolean connected(int x, int y) {return find(x) find(y);}
}二. 运用案例 - 省份数量
原题链接 我们在并查集模板的基础上进行改造
class UnionFind {private int[] rank;// 每个省份具有的城市数量private int[] parent;// 每个城市对应的根节点省份private int sum;// 省份的数量public UnionFind(int[][] isConnected) {int len isConnected.length;// 初始化省份数量和提供的城市数量一致sum len;// 每个集合具有的城市数量为1rank new int[len];parent new int[len];Arrays.fill(rank, 1);// 根节点指向自己for (int i 0; i len; i) {parent[i] i;}}public int find(int x) {while (x ! parent[x]) {x parent[x];}return x;}public void union(int x, int y) {int rootX find(x);int rootY find(y);// 如果两个元素的根节点一致不需要合并if (rootX rootY) {return;}// 如果根节点 rootX 的深度 rootY。if (rank[rootX] rank[rootY]) {// 那么将以rootY作为根节点的集合加入到rootX对应的集合当中rank[rootX] rank[rootY];// 同时改变rootY的根节点指向rootX。parent[rootY] rootX;} else {// 反之rank[rootY] rank[rootX];parent[rootX] rootY;}// 合并成功那么总集合数量要减1sum--;}
}不过本题目当中对于rank这个属性没有什么作用最终看的是sum属性。因此大家可以把这个属性相关的给去除。
最后来看代码部分
public int findCircleNum(int[][] isConnected) {// 初始化构造UnionFind unionFind new UnionFind(isConnected);int len1 isConnected.length;int len2 isConnected[0].length;for (int i 0; i len1; i) {for (int j 0; j len2; j) {// 如果是相连的那么将城市 i 和 j 合并if (isConnected[i][j] 1) {unionFind.union(i, j);}}}// 最后返回集合个数即省份的个数return unionFind.sum;
}最终代码如下
public class Test547 {public int findCircleNum(int[][] isConnected) {UnionFind unionFind new UnionFind(isConnected);int len1 isConnected.length;int len2 isConnected[0].length;for (int i 0; i len1; i) {for (int j 0; j len2; j) {// 如果是相连的那么将城市 i 和 j 合并if (isConnected[i][j] 1) {unionFind.union(i, j);}}}return unionFind.sum;}class UnionFind {private int[] rank;// 每个省份具有的城市数量private int[] parent;// 每个城市对应的根节点省份private int sum;// 省份的数量public UnionFind(int[][] isConnected) {int len isConnected.length;// 初始化省份数量和提供的城市数量一致sum len;// 每个集合具有的城市数量为1rank new int[len];parent new int[len];Arrays.fill(rank, 1);// 根节点指向自己for (int i 0; i len; i) {parent[i] i;}}public int find(int x) {while (x ! parent[x]) {x parent[x];}return x;}public void union(int x, int y) {int rootX find(x);int rootY find(y);// 如果两个元素的根节点一致不需要合并if (rootX rootY) {return;}// 如果根节点 rootX 的深度 rootY。if (rank[rootX] rank[rootY]) {// 那么将以rootY作为根节点的集合加入到rootX对应的集合当中rank[rootX] rank[rootY];// 同时改变rootY的根节点指向rootX。parent[rootY] rootX;} else {// 反之rank[rootY] rank[rootX];parent[rootX] rootY;}sum--;}}
}
