并查集
模板
问题描述
给定若干组随机的两两有关系的元素之后。输入一组元素,要求判断相互之间是否有关系(关系具有传递性)。
思路
将每一个关系网总结为一个关系集合,用集合中的某一个元素代表根节点,建立一个树状结构,判断二元素有无关系只需观察二元素根节点是否相同。
如果需要添加一组“元素关系”与另一组“元素关系”即进行UNION操作,则只要对二根节点进行操作,判断哪一个根节点作为新的父节点即可,此时有两种优化方式:一是通过size优化,根节点少的作为根节点多的的子节点,二是通过rank优化,树高度较低的作为高度较高的子节点,二者产生的均为相对最优解。
代码模板
普通方式
class DSU{//Disjoint Set Union模板
int[] parent;
public DSU(int N)//初始化,将所有节点父节点设为自己
{
parent = new int[N];
for(int i =0;i<N;i++)
{parent[i]=i;}
}
public int find(int x)//找根节点
{
if (parent[x]!=x)
{
parent[x]=find(parent[x]);
}
return parent[x];
}
public void union(int x,int y)//并集操作,将二者置为有关系
{
parent[find(x)]= find(y);
}
}
优化1(size)
class DSU{//Disjoint Set Union模板
int[] parent;
int[] size;
public DSU(int N)//初始化,将所有节点父节点设为自己
{
parent = new int[N];
size = new int[N];
for(int i =0;i<N;i++)
{parent[i]=i;}
Arrays.fill(size,1);//初始化,置1
}
public int find(int x)//找根节点
{
if (parent[x]!=x)
{
parent[x]=find(parent[x]);
}
return parent[x];
}
public void union(int x,int y)//并集操作,将二者置为有关系
{ int rootx = find(x);
int rooty = find(y);
if(rootx==rooty) return;
if(size[rootx]<=size[rooty])
{
parent[rootx] = rooty;
size[rooty]+=size[rootx];//判断谁节点更多,由节点更多的作为父节点
}
else if(size[rootx]> size[rooty])
{
parent[rooty] = rootx;
size[rootx]+=size[rooty];//判断谁节点更多,由节点更多的作为父节点
}
}
}
优化2(rank)
class DSU{//Disjoint Set Union模板
int[] parent;
int[] rank;
public DSU(int N)//初始化,将所有节点父节点设为自己
{
parent = new int[N];
size = new int[N];
for(int i =0;i<N;i++)
{parent[i]=i;}
Arrays.fill(rank,1);//初始化,置1
}
public int find(int x)//找根节点
{
if (parent[x]!=x)
{
parent[x]=find(parent[x]);
}
return parent[x];
}
public void union(int x,int y)//并集操作,将二者置为有关系
{ int rootx = find(x);
int rooty = find(y);
if(rootx==rooty) return;
if(rank[rootx]<rank[rooty])
{
parent[rootx] = rooty;
}
else if(rank[rootx]> rank[rooty])
{
parent[rooty] = rootx;
}
else
{
parent[rooty] = rootx;
rank++;//仅深度相等时需要维护
}
}
}
例题:[305. 岛屿数量 II]
题目描述:
给你一个大小为 m x n 的二进制网格 grid 。网格表示一个地图,其中,0 表示水,1 表示陆地。最初,grid 中的所有单元格都是水单元格(即,所有单元格都是 0)。
可以通过执行 addLand 操作,将某个位置的水转换成陆地。给你一个数组 positions ,其中 positions[i] = [ri, ci] 是要执行第 i 次操作的位置 (ri, ci) 。
返回一个整数数组 answer ,其中 answer[i] 是将单元格 (ri, ci) 转换为陆地后,地图中岛屿的数量。
岛屿 的定义是被「水」包围的「陆地」,通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。
输入: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 个岛屿。
输入:m = 1, n = 1, positions = [[0,0]]
输出:[1]
提示:
1 <= m, n, positions.length <= 104
1 <= m * n <= 104
positions[i].length == 2
0 <= ri < m
0 <= ci < n
import java.util.ArrayList;
import java.util.List;
class Solution {
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};//位置坐标变换
public List<Integer> numIslands2(int m, int n, int[][] positions) {
DSU dsu = new DSU(m*n);
boolean[][] island = new boolean[m][n];
List<Integer> res = new ArrayList<>();
int count = 0;
for(int []cur:positions)//对于position中每一个操作位置进行操作, 产生岛屿
{
if(island[cur[0]][cur[1]])
{
res.add(count);//加入了一个岛屿
continue;
}
island[cur[0]][cur[1]] = true;//将岛屿操作中所经历的点置为true
count++;//岛屿增加
for(int[] dir:dirs)//判断是否相连
{
int x =cur[0]+dir[0];//同行点的横坐标
int y =cur[1]+dir[1];//同列点的纵坐标
if(x <0||x==m||y<0||y==n||!island[x][y])//出边界或者该地未被变为岛屿
{
continue;
}
int component1 = dsu.find(cur[0]*n+cur[1]);//找到位置1:position中的操作位置
int component2 = dsu.find(x*n+y);//找到位置2:循环中有x与y的位置
if(component1!=component2)
{
dsu.union(component1,component2);//设定1与2有关系,使二者根节点相同(将1与2合并为同一岛屿)
count--;//岛屿数减1
}
}
res.add(count);
}return res;
}
class DSU{//Disjoint Set Union模板
int[] parent;
public DSU(int N)//初始化,将所有节点父节点设为自己
{
parent = new int[N];
for(int i =0;i<N;i++)
{parent[i]=i;}
}
public int find(int x)//找根节点
{
if (parent[x]!=x)
{
parent[x]=find(parent[x]);
}
return parent[x];
}
public void union(int x,int y)
{
parent[find(x)]= find(y);
}//岛屿长度较小,暂时没有优化
}
}