并查集及应用

本文主要是介绍并查集及应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.实现

package leetcode.algo.unionfind;public class UnionFind {// 连通分量个数private int count;// 存储一棵树private int[] parent;// 记录树的“重量”private int[] size;public UnionFind(int n) {this.count = n;parent = new int[n];size = new int[n];for (int i = 0; i < n; i++) {// 初始化根节点指向自己parent[i] = i;size[i] = 1;}}public void union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ) {return;}// 小树接到大树下面，较平衡(这里属于优化逻辑)if (size[rootP] > size[rootQ]) {parent[rootQ] = rootP;size[rootP] += size[rootQ];} else {parent[rootP] = rootQ;size[rootQ] += size[rootP];}count--;}// 判断是否连通public boolean connected(int p, int q) {int rootP = find(p);int rootQ = find(q);return rootP == rootQ;}private int find(int x) {while (parent[x] != x) {// 进行路径压缩parent[x] = parent[parent[x]];x = parent[x];}return x;}public int count() {return count;}}

2. 应用

2.1 有向无环图是否有环？

public boolean containsCircle(int[][] M) {int n = M.length;UnionFind uf = new UnionFind(n);for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (M[i][j] == 1) {if (i !=j && uf.connected(i, j)) {return true;}uf.union(i, j);}}}return false;}public static void main(String[] args) {int[][] M = {{1, 1, 0},{0, 0, 0},{0, 0, 1}};UnionFind uf = new UnionFind(3);System.out.println(uf.containsCircle(M));}

2.2 连通分量的数量

    public int findCircleNum(int[][] M) {int n = M.length;UnionFind uf = new UnionFind(n);for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (M[i][j] == 1) {uf.union(i, j);}}}return uf.count();}public static void main(String[] args) {int[][] M = {{1, 1, 0},{1, 1, 0},{0, 0, 1}};UnionFind uf = new UnionFind(3);System.out.println(uf.findCircleNum(M));}

这篇关于并查集及应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---