使用并查集解决的相关问题

作者: Grey

原文地址：使用并查集解决的相关问题

关于并查集的说明，见如下博客：

使用并查集处理集合的合并和查询问题

相关题目

LeetCode 200. 岛屿数量

本题的解题思路参考博客

使用DFS和并查集方法解决岛问题

LeetCode 547. 省份数量

主要思路

横纵坐标表示的是城市，因为城市是一样的，所以只需要遍历对角线上半区或者下半区即可，如果某个(i,j)位置是1，可以说明如下两个情况

第一，i这座城市和j这座城市可以做union操作。

第二，(j,i)位置一定也是1。

遍历完毕后，返回整个并查集中的集合数量即可。

完整代码

public static int findCircleNum(int[][] m) {         int n = m.length;         UF uf = new UF(n);         for (int i = 0; i < n; i++) {             for (int j = i + 1; j < n; j++) {                 if (m[i][j] == 1) {                     uf.union(i, j);                 }             }         }         return uf.setSize();     }      public static class UF {         int[] parent;         int[] help;         int[] size;         int sets;          public UF(int n) {             size = new int[n];             parent = new int[n];             help = new int[n];             for (int i = 0; i < n; i++) {                 parent[i] = i;                 size[i] = 1;             }             sets = n;         }          public void union(int i, int j) {             if (i == j) {                 return;             }             int p1 = find(i);             int p2 = find(j);             if (p2 != p1) {                 int size1 = size[p1];                 int size2 = size[p2];                 if (size1 > size2) {                     parent[p2] = p1;                     size[p1] += size2;                 } else {                     parent[p1] = p2;                     size[p2] += size1;                 }                 sets--;             }         }          public int find(int i) {             int hi = 0;             while (i != parent[i]) {                 help[hi++] = i;                 i = parent[i];             }             for (int index = 0; index < hi; index++) {                 parent[help[index]] = i;             }             return i;         }          public int setSize() {             return sets;         }     } 

待更新...

更多

算法和数据结构笔记