并查集
并查集定义
- 并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。
- 并查集通常包含两种操作 查找(Find)：查询两个元素是否在同一个集合中 合并(Union)：把两个不相交的集合合并为一个集合
结构
给集合中的元素包一层Node
public class Code05_UnionFind{
public static class Node<V>{
V value;
public Node(V v){this.value = v;}
}
public static class UnionFind<V>{
public HashMap<V,Node<V>> nodes;
public HashMap<Node<V>,Node<V>> parents;
public HashMap<Node<V>,Integer> sizeMap;
//初始化并查集,根据集合中的元素初始化，父亲都是他自己，sizeMap则都是1
public UnionFind(List<V> value){
nodes = new HashMap<>();
parents = new HashMap<>();
sizeMap = new HashMap<>();
for(V cur : value){
Node<V> node = new Node<>(cur);
nodes.put(cur,node);
parents.put(node,node);
sizeMap.put(node,1);
}
}
//找寻自己的父亲,并且进行路径压缩
public Node<V> findFather(Node<V> cur){
Stack<Node<V>> 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 boolean isSameSet(V a,V b){
return findFather(nodes.get(a)) == findFather(nodes.get(b));
}
public void union(V a,V b){
Node<V> aHead = findFather(nodes.get(a));
Node<V> bHead = findFather(nodes.get(b));
if(aHead != bHead){
int aSetSize = sizeMap.get(aHead);
int bSetSize = sizeMap.get(bHead);
//决定谁挂在谁上面
Node<V> bigNode = aSetSize >= bSetSize ? aHead : bHead;
Node<V> smallNode = bigNode == aHead ? bHead : aHead;
sizeMap.put(bigNode,aSetSize+bSetSize);
parents.put(smallNode,bigNode);
sizeMap.remove(smallNode);
}
}
public int sets(){
return sizeMap.size();
}
}
}
题目
省份数量
题目：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-provinces
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
思路
- 直接用并查集思路
- n * n矩阵必然对角线对称的，因此，只需要遍历对角线以下的城市，就能知道多少省份
- n个城市，因此可以直接根据n，初始化一个数组，数组下标表示数组中对应城市i
- i * j=1，则直接将i和junion，遍历完所有数组，直接返回sets，就能得到答案
public class code01_FriendCircles{
//当前UnionFind结构
public static class UnionFind{
//parnet[i] = k,i的父亲是k
private int[] parent;
//size[i] = k,表明当前头结点有多少元素
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;
size[i] = 1;
}
}
//从i开始往上找集合头元素，需要做路径压缩
public int find(int n){
int hi = 0;
while(n != parent[n]){
help[hi++] = n;
n = parent[n];
}
for(int i = 0;i < hi;i++){
parent[help[i]] = n;
}
return n;
}
//合并
public void union(int i,int j){
int iH = find(i);
int jH = find(j);
if(iH != jH){
int iSize = size[iH];
int jSize = size[jH];
sets--;
if(iSize >= jSize){
parent[jH] = iH;
size[iH] += size[jH];
} else {
parent[iH] = jH;
size[jH] += size[iH];
}
}
}
public int sets(){
return sets;
}
}
//题解
public static int findCircleNum(int[][] M){
int n = M.length;
UnionFind uf = new UnionFind(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.sets();
}
}
岛屿数量
给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
- 用并查集去解这道题
- 坐标直接用dots代替，声明一个类dots，数组中每个元素对应一个dot，凡是等于1的，说明是陆地，生成对应的dot数组
- 循环数组grid，凡是1的，则对dots数组中dot进行union
- 最后，返回sets
public static class Dot{
}
public static class Node<V>{
V value;
public Node(V v){value = v;}
}
public static class unionFind1<V>{
private HashMap<V,Node<V>> nodes;
private HashMap<Node<V>,Node<V>> parents;
private HashMap<Node<V>,Integer> sizeMap;
public unionFind1(List<V> list){
nodes = new HashMap<>();
parents = new HashMap<>();
sizeMap = new HashMap<>();
for(V cur : list){
Node<V> node = new Node<>(cur);
nodes.put(cur,node);
parents.put(cur,cur);
sizeMap.put(cur,1);
}
}
//找寻头节点，并压缩路径
public Node<V> fintFather(Node<V> cur){
Stack<V> 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){
Node<V> aHead = findFather(nodes.get(a));
Node<V> bHead = findFather(nodes.get(b));
if(aHead != bHead){
int aSize = sizeMap.get(aHead);
int bSize = sizeMap.get(bHead);
Node<V> big = aSize >= bSize? aHead:bHead;
Node<V> small = big == aHead? bHead:aHead;
parents.put(small,big);
sizeMap.put(big,aSize+bSize);
sizeMap.remove(small);
}
}
public int sets(){
return sizeMap.size();
}
}
public static int numIslands1(char[][] board){
int r = board.length;
int c = board[0].length;
//用坐标表示dots，当前的元素
Dot[][] dots = new Dot[r][c];
List<Dot> list = new ArrayList<>();
for(int i = 0 ; i < r;i++){
for(int j = 0; j < c;j++){
if(board[i][j] == 1){
dots[i][j] = new Dot();
list.add(dots[i][j]);
}
}
}
//初始化并查集
UnionFind1<Dot> uf1 = new UnionFind1<>(list);
//扫描每个元素和他左上元素之间的关系，最左和最上单独for循环
for(int i = 1 ; i < c;i++){
if(board[0][i-1] == '1' && board[0][i] == '1'){
uf1.union(dots[0][i-1],dots[0][i]);
}
}
for(int i = 1; i < r;i++){
if(board[i - 1][0] == '1' && board[i][0] == '1'){
uf1.union(dots[i-1][i],dots[i][0]);
}
}
for(int i = 1;i < r;i++){
for(int j = 1;j < c;j++){
if(board[i][j] == '1'){
if(board[i][j-1] == '1'){
uf1.union(dots[i][j-1],dots[i][j]);
}
if(board[i-1][j] == '1'){
uf1.union(dots[i-1][j],dots[i][j]);
}
}
}
}
return uf1.sets();
}
思路二：
- 针对HashMap比数组效率低的问题，用数组表示（x，y）元素
- 初始化数组的长度是row*col,然后每个节点映射到数组上的公式是row * col + col
public static class UnionFind2{
private int[] help;
//对应头结点
private int[] parents;
//对应集合的元素
private int[] size;
//对应多少个集合
private int sets;
//初始化
public UnionFind2(char[][] board){
int r = board.length;
int c = board[0].length;
int len = r * c;
parents = new int[len];
size = new int[len];
for(int i = 0; i < r;i++){
for(int j = 0;j < c;j++){
if(board[i][j] == '1'){
int index = index(i,j);
parents[index] = index;
size[index] = 1;
sets++;
}
}
}
}
//根据r，c找到对应的parents下标
private int index(int r,int c){
return r *c +c;
}
private int find(int n){
int hi = 0;
while( n != parents[n]) {
help[hi++] = n;
n = parents[n];
}
for(int i = 0;i < hi;i++){
parents[help[i]] = n;
}
return n;
}
public void union(int r1,int c1,int r2,int c2){
int f1 = index(r1,c1);
int f2 = index(r2,c2);
f1 = find(f1);
f2 = find(f2);
if( f1 != f2){
int s1 = size[f1];
int s2 = size[f2];
sets--;
if(s1 >= s2){
parents[f2] = f1;
size[f1] += size[f2];
} else {
parents[f1] = f2;
size[f2] += size[f1];
}
}
}
public int sets(){
return sets;
}
}
public static int numIslands2(char[][] board){
int r = board.length;
int c = board[0].length;
//初始化uf
UnionFind2 uf = new UnionFind2(board);
for(int i = 1 ; i < r;i++){
if(board[0][i -1] == '1' && board[0][i] == '1'){
uf.union(0,i-1,0,i);
}
}
for(int j = 1;j < c;j++){
if(board[j-1][0] == '1' && board[j][0] == '1'){
uf.union(j-1,0,j,0);
}
}
for(int i= 1;i < r;i++){
for(int j = 1;j < r;j++){
if(board[i][j] == 1){
if(board[i-1][j] == 1){
uf.union(i-1,j,i,j);
}
if(board[i][j-1] == 1){
uf.union(i,j-1,i,j);
}
}
}
}
return uf.sets;
}
思路
- 感染法，将第一个遇到的陆地全部感染成0，然后ans++
- 循环遍历整个二维数组
- 返回ans
public static int numIslands3(char[][] board){
int ans = 0;
int r = board.length;
int c = board.length;
for(int i = 0;i < r;i++){
for(int j = 0;j < c;j++){
if(board[i][j] == '1'){
//感染
infect(i,j,board);
//统计
ans++;
}
}
}
return ans;
}
public static void infect(int i,int j,char[][] board){
if(i < 0 || i==board.length || j <0 || j == board[i].length || board[i][j] == '0'){
return;
}
board[i][j] = 0;
infect(i-1,j,board);
infect(i+1,j,board);
infect(i,j-1,board);
infect(i,j+1,board);
}
岛屿数量2
给你一个大小为 m x n 的二进制网格 grid 。网格表示一个地图，其中，0 表示水，1 表示陆地。最初，grid 中的所有单元格都是水单元格（即，所有单元格都是 0）。
可以通过执行 addLand 操作，将某个位置的水转换成陆地。给你一个数组 positions ，其中 positions[i] = [ri, ci] 是要执行第 i 次操作的位置 (ri, ci) 。
返回一个整数数组 answer ，其中 answer[i] 是将单元格 (ri, ci) 转换为陆地后，地图中岛屿的数量。
岛屿 的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。
示例 1：
输入：m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
输出：[1,1,2,3]
解释：
起初，二维网格grid被全部注入「水」。（0 代表「水」，1 代表「陆地」）
- 操作#1：addLand(0, 0) 将grid[0][0] 的水变为陆地。此时存在 1 个岛屿。
- 操作#2：addLand(0, 1) 将grid[0][1] 的水变为陆地。此时存在 1 个岛屿。
- 操作#3：addLand(1, 2) 将grid[1][2] 的水变为陆地。此时存在 2 个岛屿。
- 操作#4：addLand(2, 1) 将grid[2][1] 的水变为陆地。此时存在 3 个岛屿。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-islands-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
- 并查集，数组长度用r*l+l
- 弄一个connect函数，传入positions变量的值，判断当前这个size是否是0，如果是0，就增加这个陆地，然后对四周进行union
public static class UnionFind1{
private int[] parents;
private int[] help;
private int[] size;
private int sets;
public UnionFind1(int m,int n){
int len = m * n;
parents = new int[len];
help = new int[len];
size = new int[len];
}
private int index (int r,int c){
return r * c + c;
}
private int find(int n){
int hi =0;
while(n != parents[n]){
help[hi]=n;
n = parents[n]
}
for(int i = 0;i < hi;i++){
parents[help[i++]] = n;
}
return n;
}
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[f1] == 0 || size[f2] == 0){
return;
}
int f1 = find(i1);
int f2 = find(i2);
if(f1 != f2){
if(size[f1] >= size[f2]){
parents[f2] = f1;
size[f1] += size[f2];
} else {
parents[f1] = f2;
size[f2] += size[f1];
}
sets--;
}
}
public int connect(int r, int c){
int in = 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;
}
public static List<Integer> numIsIands21(int m,int n ,int[][] positions){
UnionFind1 uf1 = new UnionFind1(m,n);
List<Integer> ans = new ArrayList<>();
for(int[] position : position){
ans.add(uf1.connect(position[0],position[1]));
}
return ans;
}
}
思路：
- m，n过大，position过少，则可以用中文替代，1_2形式表示，
- parents用hashMap<String,String>表示
public static class UnionFind2{
private HashMap<String,String> parent;
private HashMap<String,Integer> size;
private ArrayList<String> 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(parents.get(cur))){
help.add(cur);
cur = parents.get(cur);
}
for(String str : help){
parent.put(str,str);
}
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.containKey(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;
}
}