并查集合(力扣)
0. 基础知识
参考基础知识博客
1. 朋友圈问题
朋友圈
班上有N名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。
如果已知A是B的朋友，B是C的朋友，那么我们可以认为A也是C的朋友。
所谓的朋友圈，是指所有朋友的集合。
给定一个N * N的矩阵M，表示班级中学生之间的朋友关系。
如果M[i][j] = 1，表示已知第i个和j个学生互为朋友关系，
否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
解题思路:
利用并查集合的思路，根据矩阵的大小初始化并查集合类，每个学生都有编号i[0~N-1]，他们表示每个独立的节点。遍历朋友关系矩阵，当矩阵中M[i][j]=1时，就把对应的学生集合合并，最后返回sizeMap.size()就是朋友圈总数。
public static class UnionFindSet{
// 记录每个节点的父节点，也就是头节点
public HashMap<Integer, Integer> fatherMap;
// 记录每个头节点的所挂节点的总个数
public HashMap<Integer, Integer> sizeMap;
// 初始化并查集合
public UnionFindSet(int N){
fatherMap = new HashMap<Integer, Integer>();
sizeMap = new HashMap<Integer, Integer>();
for (int i=0; i<N; i++){
fatherMap.put(i, i);
sizeMap.put(i ,1);
}
}
// 找到给定的节点的父节点
public int findFather(int node){
// 把向上找的过程中，沿途的点都放在path里
Deque<Integer> stack = new ArrayDeque<>();
while (node != fatherMap.get(node)){
stack.push(node);
node = fatherMap.get(node);
}
// 沿途节点，更改父亲节点
while (!stack.isEmpty()){
fatherMap.put(stack.pop(), node);
}
return node;
}
// 判断两个节点是否是一个集合
public boolean isSameSet(int a, int b){
return findFather(a) == findFather(b);
}
// 合并给定的两个节点
public void union(int a, int b){
int aF = findFather(a);
int bF = findFather(b);
// 不在一个集合，需要合并
if (aF != bF){
// 小节点挂在大节点上
int big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
int small = big == aF ? bF : aF;
// 修改small的节点，挂在big上
fatherMap.put(small, big);
// 接受两个链表的和
sizeMap.put(big, sizeMap.get(big) + sizeMap.get(small));
sizeMap.remove(small);
}
}
// 查询最后父节点的数目，也就是合并后，不相通的集合数量
public int getNum(){
return sizeMap.size();
}
}
public static void main(String[] args) {
int [][] M1 = {{1,1,0},
{1,1,1},
{0,1,1}};
UnionFindSet unionFindSet = new UnionFindSet(M1.length);
for (int i=0; i<M1.length; i++){
for (int j=0; j<M1.length; j++){
if (i!=j && M1[i][j]==1){
unionFindSet.union(i, j);
}
}
}
System.out.println(unionFindSet.getSize());
} 消息团队通知
腾讯笔试
大团队有n个人，m个小团队。每个小团队的人数和编号已知。向编号0发送一个通知，所有和编号0同属于一个小团队都会知道，小团队中的人还会告知他们所属的小团队。现在想知道最后会有多少个人直到通知？
输入：
第一行输入两个，团队总人数和小团队数目
剩下的行，第一个数是小团队的总人数，然后依次是小团队人员编号
50 5
2 1 2
5 10 11 12 13 14
2 0 1
2 49 2
4 6 7 8 2
返回: 7, 通知到的人是: 0 1 2 6 7 8 49
解题思路:
可以用并查集合解决，建立和初始化一个大小为总人数的并查集合。每次输入的一整行相互之间合并组成一个集合，后面的行(小团队)如果有之前团队成员的编号就会自动合并成更大的集合，最后统计编号0所在的父节点的sizeMap.size()就是最后的人数。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
UnionFindSet unionFindSet = new UnionFindSet(n);
List<List<Integer>> list = new ArrayList<>();
while (m-- > 0){
int groupLength = sc.nextInt();
List<Integer> subList = new ArrayList<>();
while (groupLength-- > 0){
subList.add(sc.nextInt());
}
for (int i=1; i<subList.size(); i++){
// 核心思想是: 合并两个节点，是合并节点所在的集合！
unionFindSet.union(subList.get(0), subList.get(i));
}
list.add(subList);
}
sc.close();
System.out.println(list);
System.out.println(unionFindSet.sizeMap.get(unionFindSet.findFather(0)));
} 2. 岛屿问题
岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
解题思路:
利用并查集合的思路，根据二维网格的大小初始化并查集合类，其中每个等于1的网格就是一个暂时独立的节点。在网格中遍历每个点，检查它的上下左右，如果有1就把它们所在的集合合并，最后岛屿的数量就是所有独立父节点的数量，也就是sizeMap.size()
public static class UnionFindSets{
// 记录每个节点的父节点，也就是头节点
public HashMap<Integer, Integer> fatherMap;
// 记录每个头节点的所挂节点的总个数
public HashMap<Integer, Integer> sizeMap;
// 初始化并查集合
public UnionFindSets(char[][] M){
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();
int rows = M.length;
int cols = M[0].length;
for (int i=0; i<rows; i++){
for (int j=0; j<cols; j++){
if (M[i][j] == '1'){
// 为每个1编号
int cur = i*cols + j;
fatherMap.put(cur, cur);
sizeMap.put(cur, 1);
}
}
}
}
public int getFather(int node){
Deque<Integer> stack = new ArrayDeque<>();
// 收集沿路的节点
while (node != fatherMap.get(node)){
stack.push(node);
node = fatherMap.get(node);
}
// 扁平化
while (!stack.isEmpty()){
fatherMap.put(stack.pop(), node);
}
return node;
}
// 判断两个节点是否是一个集合
public boolean isSameSet(int a, int b){
return getFather(a) == getFather(b);
}
public void union(int a, int b){
int aF = getFather(a);
int bF = getFather(b);
// 不在一个集合，需要合并
if (aF != bF){
// 小节点挂在大节点上
int big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
int small = big == aF ? bF : aF;
// 修改small的节点，挂在big上
fatherMap.put(small, big);
// 接受两个链表的和
sizeMap.put(big, sizeMap.get(big) + sizeMap.get(small));
sizeMap.remove(small);
}
}
// 查询最后父节点的数目，也就是合并后，不相通的集合数量
public int getSize(){
return sizeMap.size();
}
}
public static void main(String[] args) {
UnionFindSets unionFindSet_1 = new UnionFindSets(grid);
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; i++){
for (int j = 0; j < cols; j++){
if (grid[i][j] == '1'){
int position = i * cols + j;
// 合并左下就可以完成检查
if ( (i+1)<rows && grid[i+1][j] == '1'){
int down = (i+1) * rows + j;
unionFindSet_1.union(position, down);
}
// 合并左下就可以完成检查
if ( (j+1)<cols && grid[i][j+1] == '1'){
int right = i * rows + j+1;
unionFindSet_1.union(position, right);
}
}
}
}
System.out.println(unionFindSet_1.getSize());
} 岛屿的最大面积
Nr. 695
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
解题思路:
和岛屿数量一致，最后在sizeMap中遍历，找到最大的value即可.
// 获得sizeMap最大的value
public int getMaxSize(){
int max = 0;
for (int cur : sizeMap.keySet()){
max = max > sizeMap.get(cur) ? max : sizeMap.get(cur);
}
return max;
} 
远景公司福利 157人发布
