php语言 网站建设,中国进出口贸易网,医疗网站建设平台价格,ftp服务器设置网站主页并查集简介
并查集#xff1a;一开始#xff0c;把a#xff0c;b#xff0c;c放入并查集#xff0c;a自己一个集合#xff0c;b自己一个#xff0c;c自己一个
提供的方法 1.boolean isSameSet(a,b)#xff0c;判断ab是否在同一个集合 2.void union(a,b),把a所…并查集简介
并查集一开始把abc放入并查集a自己一个集合b自己一个c自己一个
提供的方法 1.boolean isSameSet(a,b)判断ab是否在同一个集合 2.void union(a,b),把a所在集合的全部和b所在集合的全部两个大集合合并
怎么实现的方法一
对于每个元素都有一个指针指向自己 查询ab是否在同一个集合对于aa往上到不能再往上的节点就是他的代表节点也就是a
b同理代表节点不同所以ab所在的集合不同
我们把一个节点往上找找到不能再往上的那个节点叫集合的代表节点
那如何实现union合并呢 并查集有自己的机制记录每一个集合大小是多少
然后unionae时把b的指针直接挂到a后面unionac时小的挂到大的上c挂到a后面
如果再unionb,d然后union(d,e)怎么union先顺着d往上找找到b然后顺着e往上找找到a小的挂大的只需改代表节点b-a,欧了 import java.util.HashMap;
import java.util.List;
import java.util.Stack;public class Code05_UnionFind {public static class NodeV {V value;public Node(V v) {value v;}}public static class UnionFindV {//搞三张表public HashMapV, NodeV nodes;public HashMapNodeV, NodeV parents;//parent表key是儿子value是父亲儿子父亲一一对应public HashMapNodeV, Integer sizeMap;//代表节点和大小size对应public UnionFind(ListV values) {//初始化nodes new HashMap();parents new HashMap();sizeMap new HashMap();for (V cur : values) {NodeV node new Node(cur);nodes.put(cur, node);parents.put(node, node);sizeMap.put(node, 1);}}// 给你一个节点请你往上到不能再往上把代表返回//找代表节点要用很多次所以把一次找一个爹优化成直接找祖宗沿一条链压入栈//一个一个弹出只要不是栈顶就挂到祖宗后面public NodeV findFather(NodeV cur) {StackNodeV path new Stack();while (cur ! parents.get(cur)) {path.push(cur);cur parents.get(cur);}//推出的时候cur parents.get(curwhile (!path.isEmpty()) {parents.put(path.pop(), cur);}return cur;}public boolean isSameSet(V a, V b) {return findFather(nodes.get(a)) findFather(nodes.get(b));}public void union(V a, V b) {NodeV aHead findFather(nodes.get(a));NodeV bHead findFather(nodes.get(b));if (aHead ! bHead) {int aSetSize sizeMap.get(aHead);int bSetSize sizeMap.get(bHead);NodeV big aSetSize bSetSize ? aHead : bHead;//就是ifabbigasmallbNodeV small big aHead ? bHead : aHead;parents.put(small, big);//小集合的头部父亲设成大集合sizeMap.put(big, aSetSize bSetSize);//大集合变大sizeMap.remove(small);}}public int sets() {return sizeMap.size();}}
}并查集应用
1.表示任务关系1代表认识0代表不认识
一定是正方形N*N且m[i][j]1,那么m[j][i]1,大正方形是对称的
求有多少个联通区朋友圈互相认识的域 用并查集从0开始0认识2认识4一合并【0.2.4】从1开始【1.3】一共两个朋友圈
// 本题为leetcode原题
// 测试链接https://leetcode.com/problems/friend-circles/
// 可以直接通过
public class Code01_FriendCircles {public static int findCircleNum(int[][] M) {int N M.length;// 初始化{0} {1} {2} {N-1}每个数据单独成一个集合UnionFind unionFind new UnionFind(N);for (int i 0; i N; i) { //行for (int j i 1; j N; j) {//列for循环只用便利右上部分因为1认识22就认识1if (M[i][j] 1) { // i和j互相认识unionFind.union(i, j);//ij合并}}}return unionFind.sets();}public static class UnionFind {//用数组代替哈希表更快// parent[i] k i的父亲是kprivate int[] parent;// size[i] k 如果i是代表节点size[i]才有意义否则无意义// i所在的集合大小是多少private int[] size;// 辅助结构作栈用private int[] help;// 一共有多少个集合private int sets;//初始化public UnionFind(int N) {parent new int[N];size new int[N];help new int[N];sets N;for (int i 0; i N; i) {parent[i] i; //i的父亲节点就是自己size[i] 1; //i自己就是代表节点大小为1}}// 从i开始一直往上往上到不能再往上代表节点返回// 这个过程要做路径压缩private int find(int i) {int hi 0;while (i ! parent[i]) {//i不等于自己的父亲i往上 help[hi] i;//help作栈i parent[i];}//直到iparent[i]也就是代表节点了for (hi--; hi 0; hi--) {parent[help[hi]] i;}return i;}public void union(int i, int j) {int f1 find(i);int f2 find(j);if (f1 ! f2) {if (size[f1] size[f2]) {size[f1] size[f2];parent[f2] f1;} else {size[f2] size[f1];parent[f1] f2;}sets--;}}public int sets() {return sets;}}}岛问题
给定一个二维数组matrix里面的值不是1就是0
上或下或左或右相邻的1认为是一片岛
返回matrix中岛的数量求几片1
思路从左往右依次遍历不是1就跳过是一就调用infection函数把与这个一相邻的1全部变成2然后往后走不是1就跳
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;// 本题为leetcode原题
// 测试链接https://leetcode.com/problems/number-of-islands/
// 所有方法都可以直接通过
public class Code02_NumberOfIslands {public static int numIslands3(char[][] board) {int islands 0;for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {if (board[i][j] 1) {//遍历是1岛的数量然后调用感染函数islands;infect(board, i, j);}}}return islands;}// 从(i,j)这个位置出发把所有练成一片的1字符变成0不是0字符而是0阿斯克码值public static void infect(char[][] board, int i, int j) {if (i 0 || i board.length || j 0 || j board[0].length || board[i][j] ! 1) {return;}board[i][j] 0;//一定要改否则无限递归infect(board, i - 1, j);infect(board, i 1, j);infect(board, i, j - 1);infect(board, i, j 1);}public static int numIslands1(char[][] board) {int row board.length;int col board[0].length;Dot[][] dots new Dot[row][col];ListDot dotList new ArrayList();for (int i 0; i row; i) {for (int j 0; j col; j) {if (board[i][j] 1) {dots[i][j] new Dot();dotList.add(dots[i][j]);}}}UnionFind1Dot uf new UnionFind1(dotList);for (int j 1; j col; j) {//第零行没有上单独拿出来// (0,j) (0,0)跳过了 (0,1) (0,2) (0,3)if (board[0][j - 1] 1 board[0][j] 1) {//自己是1右边也是1就合并uf.union(dots[0][j - 1], dots[0][j]);}}for (int i 1; i row; i) {{//第零列没有左单独拿出来if (board[i - 1][0] 1 board[i][0] 1) {uf.union(dots[i - 1][0], dots[i][0]);}}for (int i 1; i row; i) {//既有左又有上for (int j 1; j col; j) {if (board[i][j] 1) {if (board[i][j - 1] 1) {uf.union(dots[i][j - 1], dots[i][j]);}if (board[i - 1][j] 1) {uf.union(dots[i - 1][j], dots[i][j]);}}}}return uf.sets();}public static class Dot {}public static class NodeV {V value;public Node(V v) {value v;}}public static class UnionFind1V {public HashMapV, NodeV nodes;public HashMapNodeV, NodeV parents;public HashMapNodeV, Integer sizeMap;public UnionFind1(ListV values) {nodes new HashMap();parents new HashMap();sizeMap new HashMap();for (V cur : values) {NodeV node new Node(cur);nodes.put(cur, node);parents.put(node, node);sizeMap.put(node, 1);}}public NodeV findFather(NodeV cur) {StackNodeV path new Stack();while (cur ! parents.get(cur)) {path.push(cur);cur parents.get(cur);}while (!path.isEmpty()) {parents.put(path.pop(), cur);}return cur;}public void union(V a, V b) {NodeV aHead findFather(nodes.get(a));NodeV bHead findFather(nodes.get(b));if (aHead ! bHead) {int aSetSize sizeMap.get(aHead);int bSetSize sizeMap.get(bHead);NodeV big aSetSize bSetSize ? aHead : bHead;NodeV small big aHead ? bHead : aHead;parents.put(small, big);sizeMap.put(big, aSetSize bSetSize);sizeMap.remove(small);}}public int sets() {return sizeMap.size();}}public static int numIslands2(char[][] board) {int row board.length;int col board[0].length;UnionFind2 uf new UnionFind2(board);for (int j 1; j col; j) {if (board[0][j - 1] 1 board[0][j] 1) {uf.union(0, j - 1, 0, j);}}for (int i 1; i row; i) {if (board[i - 1][0] 1 board[i][0] 1) {uf.union(i - 1, 0, i, 0);}}for (int i 1; i row; i) {for (int j 1; j col; j) {if (board[i][j] 1) {if (board[i][j - 1] 1) {uf.union(i, j - 1, i, j);}if (board[i - 1][j] 1) {uf.union(i - 1, j, i, j);}}}}return uf.sets();}public static class UnionFind2 {//把二维数组转成一维对二维数组ij-i*列jprivate int[] parent;private int[] size;private int[] help;private int col;//列private int sets;//集合数量public UnionFind2(char[][] board) {col board[0].length;sets 0;int row board.length;int len row * col;//一共有几个数parent new int[len];size new int[len];help new int[len];for (int r 0; r row; r) {//初始化for (int c 0; c col; c) {if (board[r][c] 1) {int i index(r, c);parent[i] i;size[i] 1;sets;}}}}// (r,c) - i用i代替rcprivate int index(int r, int c) {//r行c列对应的下标return r * col c;}// 原始位置 - 下标private int find(int i) {int hi 0;while (i ! parent[i]) {help[hi] i;i parent[i];}for (hi--; hi 0; hi--) {parent[help[hi]] i;}return i;}public void union(int r1, int c1, int r2, int c2) {int i1 index(r1, c1);int i2 index(r2, c2);int f1 find(i1);int f2 find(i2);if (f1 ! f2) {if (size[f1] size[f2]) {size[f1] size[f2];parent[f2] f1;} else {size[f2] size[f1];parent[f1] f2;}sets--;}}public int sets() {return sets;}}// 为了测试public static char[][] generateRandomMatrix(int row, int col) {char[][] board new char[row][col];for (int i 0; i row; i) {for (int j 0; j col; j) {board[i][j] Math.random() 0.5 ? 1 : 0;}}return board;}// 为了测试public static char[][] copy(char[][] board) {int row board.length;int col board[0].length;char[][] ans new char[row][col];for (int i 0; i row; i) {for (int j 0; j col; j) {ans[i][j] board[i][j];}}return ans;}// 为了测试public static void main(String[] args) {int row 0;int col 0;char[][] board1 null;char[][] board2 null;char[][] board3 null;long start 0;long end 0;row 1000;col 1000;board1 generateRandomMatrix(row, col);board2 copy(board1);board3 copy(board1);System.out.println(感染方法、并查集(map实现)、并查集(数组实现)的运行结果和运行时间);System.out.println(随机生成的二维矩阵规模 : row * col);start System.currentTimeMillis();System.out.println(感染方法的运行结果: numIslands3(board1));end System.currentTimeMillis();System.out.println(感染方法的运行时间: (end - start) ms);start System.currentTimeMillis();System.out.println(并查集(map实现)的运行结果: numIslands1(board2));end System.currentTimeMillis();System.out.println(并查集(map实现)的运行时间: (end - start) ms);start System.currentTimeMillis();System.out.println(并查集(数组实现)的运行结果: numIslands2(board3));end System.currentTimeMillis();System.out.println(并查集(数组实现)的运行时间: (end - start) ms);System.out.println();row 10000;col 10000;board1 generateRandomMatrix(row, col);board3 copy(board1);System.out.println(感染方法、并查集(数组实现)的运行结果和运行时间);System.out.println(随机生成的二维矩阵规模 : row * col);start System.currentTimeMillis();System.out.println(感染方法的运行结果: numIslands3(board1));end System.currentTimeMillis();System.out.println(感染方法的运行时间: (end - start) ms);start System.currentTimeMillis();System.out.println(并查集(数组实现)的运行结果: numIslands2(board3));end System.currentTimeMillis();System.out.println(并查集(数组实现)的运行时间: (end - start) ms);}}拓展如果matrix极大 设计一种可行的并行方案
空降问题 import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;// 本题为leetcode原题
// 测试链接https://leetcode.com/problems/number-of-islands-ii/
// 所有方法都可以直接通过
public class Code03_NumberOfIslandsII {public static ListInteger numIslands21(int m, int n, int[][] positions) {UnionFind1 uf new UnionFind1(m, n);ListInteger ans new ArrayList();for (int[] position : positions) {ans.add(uf.connect(position[0], position[1]));}return ans;}public static class UnionFind1 {private int[] parent;private int[] size;//区别变化之后不在抹去size因为要用size做标记//size0代表没有初始化过没有空降过1private int[] help;private final int row;private final int col;private int sets;public UnionFind1(int m, int n) {row m;col n;sets 0;int len row * col;parent new int[len];size new int[len];help new int[len];}private int index(int r, int c) {return r * col c;}private int find(int i) {int hi 0;while (i ! parent[i]) {help[hi] i;i parent[i];}for (hi--; hi 0; hi--) {parent[help[hi]] i;}return i;}private void union(int r1, int c1, int r2, int c2) {if (r1 0 || r1 row || r2 0 || r2 row || c1 0 || c1 col || c2 0 || c2 col) {return;//检查越界}int i1 index(r1, c1);int i2 index(r2, c2);if (size[i1] 0 || size[i2] 0) {return;}int f1 find(i1);int f2 find(i2);if (f1 ! f2) {if (size[f1] size[f2]) {size[f1] size[f2];parent[f2] f1;} else {size[f2] size[f1];parent[f1] f2;}sets--; }public int connect(int r, int c) {int index index(r, c);if (size[index] 0) {//为零代表第一次来到这个位置 parent[index] index;size[index] 1;sets;union(r - 1, c, r, c);union(r 1, c, r, c);union(r, c - 1, r, c);union(r, c 1, r, c);}return sets;}}// 课上讲的如果m*n比较大会经历很重的初始化而k比较小怎么优化的方法public static ListInteger numIslands22(int m, int n, int[][] positions) {UnionFind2 uf new UnionFind2();ListInteger ans new ArrayList();for (int[] position : positions) {ans.add(uf.connect(position[0], position[1]));}return ans;}public static class UnionFind2 {//m*n很大key相对不大private HashMapString, String parent;//字符串他爹private HashMapString, Integer size;private ArrayListString help;private int sets;public UnionFind2() {parent new HashMap();size new HashMap();help new ArrayList();sets 0;}private String find(String cur) {while (!cur.equals(parent.get(cur))) {help.add(cur);cur parent.get(cur);}for (String str : help) {parent.put(str, cur);}help.clear();return cur;}private void union(String s1, String s2) {if (parent.containsKey(s1) parent.containsKey(s2)) {String f1 find(s1);String f2 find(s2);if (!f1.equals(f2)) {int size1 size.get(f1);int size2 size.get(f2);String big size1 size2 ? f1 : f2;String small big f1 ? f2 : f1;parent.put(small, big);size.put(big, size1 size2);sets--;}}}public int connect(int r, int c) {String key String.valueOf(r) _ String.valueOf(c);if (!parent.containsKey(key)) {//之前没空降过的parent.put(key, key);size.put(key, 1);sets;String up String.valueOf(r - 1) _ String.valueOf(c);String down String.valueOf(r 1) _ String.valueOf(c);String left String.valueOf(r) _ String.valueOf(c - 1);String right String.valueOf(r) _ String.valueOf(c 1);union(up, key);union(down, key);union(left, key);union(right, key);}return sets;}}}
