并查集练习

基础知识概念

理解：

并查集（Dijoint Set）属于一种跳跃式数据结构，也就是说你不会就是你压根都不会，你要是一会的就会用就行了，它没有太多让你在上面进行发展的空间，或者是需要像动态规划或者是各种搜索一样有非常强的随机应变和在上面进行自由发挥的空间。所以我们主要就是把它的情景和它的实现代码进行学习掌握。掌握代码模版直接套上去用即可。

使用场景：

它解决的场景就是组团和配对的问题，也就是说在有些现实的问题中，你需要很快地判断这两个个体是不是在一个集合中，这么讲有点抽象，很多时候就是说你和他是不是朋友这么一个问题，如果是在社交网络里面以及判断两个群组之间，是不是一个群组以及很快速地合并群组，所以需要用这样的数据结构。

并查集和叫做不相交集合（Disjoint Set）

并查集有2个核心操作

1. 查找（Find）：查找元素所在的集合（这里的集合并不是特指Set这种数据结构，是指广义上的数据集合）
2. 合并（Union）：将两个元素所在的集合合并为一个集合

并查集有2种常见的实现思路

1. Quick Find
   • 查找（Find）的时间复杂度为：O(1)
   • 合并（Union）的时间复杂度为：O(n)
2. Quick Union
   • 查找（Find）的时间复杂度为：O(logn)，可以优化至O(α(n))，α(n) ＜ 5
   • 合并（Union）的时间复杂度为：O(logn)，可以优化至O(α(n))，α(n) ＜ 5

所以，通过Quick Find来实现并查集的话，查找的效率会比Quick Union高，但是合并效率会比Quick Union低，那在开发中用哪一个呢？在开发中，一般使用Quick Union这种思路

基本操作：

并查集要解决这类场景，主要有三个要实现的函数：

• makeSet(s) : 建立一个新的并查集，其中包含 s 个单元素集合。
• unionSet(x,y) : 把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交，如果相交则不合并。
• find(x) : 找到元素 x 所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。

路径压缩

还有一个叫做所谓的路径压缩，这里的话我们看到：

• d 的 parent 是 c
• c 的 parent 是 b
• b 的 parent 是 a 那么我们可以直接把这条路上的所有元素，它的 parent 都指向 a。这样的话还是和原来的表是一样，但是它的查询时间会快不少。

练习题1：

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

深搜解法：

class Solution {List<Integer> list = new ArrayList<>();public int findCircleNum(int[][] isConn) {int row = isConn.length;int column = isConn[0].length;int res = 0;for(int i = 0;i < row;i++){if(isConn[i][i] == 1 && !list.contains(i)){list.add(i);dfs(isConn,i,res);res++;}}return res;}public void dfs(int [][]con,int city,int res){for(int i = 0;i < con[city].length;i++){if(con[city][i] == 1 && !list.contains(i)){list.add(i);dfs(con,i,res);}}}
}

广搜解法：

class Solution {public int findCircleNum(int[][] isConnected) {int provinces = isConnected.length;boolean[] visited = new boolean[provinces];int circles = 0;Queue<Integer> queue = new LinkedList<Integer>();for (int i = 0; i < provinces; i++) {if (!visited[i]) {queue.offer(i);while (!queue.isEmpty()) {int j = queue.poll();visited[j] = true;for (int k = 0; k < provinces; k++) {if (isConnected[j][k] == 1 && !visited[k]) {queue.offer(k);}}}circles++;}}return circles;}
}

并查集解法：

class Solution {public int findCircleNum(int[][] isConnected) {int provinces = isConnected.length;int[] parent = new int[provinces];for (int i = 0; i < provinces; i++) {parent[i] = i;}for (int i = 0; i < provinces; i++) {for (int j = i + 1; j < provinces; j++) {if (isConnected[i][j] == 1) {union(parent, i, j);}}}int circles = 0;for (int i = 0; i < provinces; i++) {if (parent[i] == i) {circles++;}}return circles;}public void union(int[] parent, int index1, int index2) {parent[find(parent, index1)] = find(parent, index2);}public int find(int[] parent, int index) {if (parent[index] != index) {parent[index] = find(parent, parent[index]);}return parent[index];}
}

并查集解法2

class Solution {public int findCircleNum(int[][] M) {if(M == null || M.length == 0){return 0;}int n = M.length;UnionFind uf = new UnionFind(n);for(int i = 0;i < n - 1;i++){for(int j = i+1;j < n;j++){if(M[i][j] == 1){uf.union(i,j);}}}return uf.count;}
}
class UnionFind{public int count = 0;public int[] parent;public UnionFind(int n){count = n;parent = new int[n];for(int i = 0;i < n;i++){parent[i] = i;}}public int find(int p){while(p != parent[p]){parent[p] = parent[parent[p]];p = parent[p];}return p;}public void union(int p,int q){int rootP = find(p);int rootQ = find(q);if(rootP == rootQ) return ;parent[rootP] = rootQ;count--;}
}