秋招突击——8/13——并查集——复习{有塔一面}——新作{亲戚关系}

引言

• 这两天准备腾讯的第二面，看了很多人的面经，发现考并查集的题目蛮多的，这里整理学习一下！

复习

并查集模板

• 这里学习了B站的麦克老师的课程，对应链接如下并查集课程。
• 对应模板代码如下

// 初始化
int fa[MAXN];
void init(int n){
	for(int i = 1;i <= n;i ++){
		fa[i] = i;
	}
}

// 路径压缩指定父节点
int find(int i){
	if(i == fa[i]){
		return i;
	]else{
		fa[i] = find[fa[i]];
		return fa[i];
	}
}

// 合并对应的节点
void union(int i ,int j){
	int i_fa = find(i); // 找到i的父节点
	int j_fa = find(j); // 找到j的父节点
	fa[i_fa] = j_fa;  // i的祖先指向j的祖先，实现合并

复习——有塔一面

• 第一次学习连接
• 第二次学习连接

• 第一个是阈值，第二个是节点的数量，后续就是具体的节点的坐标，如果节点的距离小于阈值，表示两者之间有关系，然后关系具有传递性！

import java.util.*;

class Main{

    static int[] fa;

    private static void init(int m){
        for(int i = 0; i < m; i++){
            fa[i] = i;
        }
    }

    private static int find(int i){
        if(fa[i] == i){
            return i;
        }else{
            fa[i] = find(fa[i]);
            return fa[i];
        }
    }

    private static void union(int i ,int j){
        int i_fa = find(i);
        int j_fa = find(j);
        fa[i_fa] = j_fa;
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        float edge = in.nextFloat();
        int m = in.nextInt();
        float[][] points = new float[m][2];
        for(int i = 0;i < m;i ++){
            points[i][0] = in.nextFloat();
            points[i][1] = in.nextFloat();
        }

        // 计算邻接矩阵
        fa = new int[m];
        init(m);
        for (int i = 0; i < points.length; i++){
            for (int j = i + 1; j < points.length; j++){
                if(Math.pow(points[i][0] - points[j][0],2) + Math.pow(points[i][1] - points[j][1],2) <= edge * edge ){
                    union(i,j);
                }
            }
        }

        // 遍历相同父子节点的点
        Map<Integer, List<Integer>> map = new HashMap<>();

        for(int i = 0;i < m;i ++) {
            map.computeIfAbsent(find(i), k -> new ArrayList<>()).add(i);
        }

        for (int x:map.keySet()){
            System.out.println(map.get(x).toString());
        }
    }
}

整体来说，并不难，实现起来，还是蛮快的，有长进，之前看了GPT的，根本看不进去，当时心里比较躁，现在好很多了！

新作

亲戚关系

• 下述题目是B站麦克老师讲算法实例题目，这里学了之后，再做一遍！
  
• 这个题目，主要是传递性，也就是并查集典型应用，如果彼此有共同的父节点，就表示是亲戚！

输入样例如下

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

具体实现代码

import java.util.Scanner;

class Main{
    private static int[] fa;

    // 并查集初始化
    private static void init(int m){
        for(int i = 1;i <= m;i ++) fa[i] = i;
    }

    // 查询父节点
    private static int find(int i){
        if(fa[i] == i)  return i;
        else {
            fa[i] = find(fa[i]);
            return fa[i];
        }
    }

    // 并查集并联
    private static void union(int i,int j){
        int i_fa = find(i);
        int j_fa = find(j);
        fa[i_fa] = j_fa;
    }

    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        fa = new int[m + 1];
        init(m );

        // 关联不同节点之间的关系
        for (int i =0;i < n;i ++) {
            int x = in.nextInt();
            int y = in.nextInt();
            union(x, y);
        }

        // 进行提问
        int count = in.nextInt();
        for(int i = 0;i < count; i++){
            int x = in.nextInt();
            int y = in.nextInt();
            if(find(x) == find(y))
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

联通图寻路问题

蚂蚁笔试第三题

总结

• 这个并查集算是做完了，但是仅仅是掌握了最基础的，怎么按秩优化还没有弄，这里先跳过吧！
• 我得专注于自身，尽力去准备，能成就成，不能成尽力就行了！