Union-Find

板子：

非递归写法（基于链表）

public class LinkedDSU {
    public static final int illegal_next=-1;
    private static class Node{
        int equiv;
        int next;
        int length;

        Node(int e,int n,int len){
            equiv = e;
            next = n;
            length = len;
        }
    }

    private final Node[] ns;

    public LinkedDSU(int n){
        ns = new Node[n];
        for (int i = 0; i < ns.length; i++) {
            ns[i] = new Node(i,illegal_next,1);
        }
    }

    public void union(int x,int y){
        // same equiv?
        int ex = find(x);
        int ey = find(y);
        if(ex == ey){
            return;
        }
        // merge small to large
        if(ns[ex].length>ns[ey].length){
            int et = ex;
            ex = ey;
            ey = et;
        }
        // change equiv
        int header = ex;
        while(ns[header].next!=illegal_next){
            ns[header].equiv = ey;
            header = ns[header].next;
        }
        ns[header].equiv = ey;
        // linked list insertion
        ns[header].next = ns[ey].next;
        ns[ey].next = ex;
        // update size
        ns[ey].length += ns[ex].length;
    }

    public int find(int x){
        return ns[x].equiv;
    }
}

递归写法

// LC765 official writeup
public class RecursiveDSU {
    private final int[] f;

    public RecursiveDSU(int n){
        f = new int[n];
        for (int i = 0; i < f.length; i++) {
            f[i] = i;
        }
    }

    public int getf(int x){
        if(f[x]==x){
            return x;
        }
        int newf = getf(f[x]);
        f[x] = newf; // path compression
        return newf;
    }

    public void add(int x,int y){
        int fx = getf(x);
        int fy = getf(y);
        f[fx] = fy;
    }
}

核心想法：如果这个元素的源头不是他自己 说明它被归到别的等价类去了，深搜它的源头（链）

多说无益，看题。

1. LC 2812 找出最安全路径

这题我一开始二分T了。预计算写的暴力，判断写的深搜。这题预计算所有点的安全距离的方式应该是多源BFS。判断连通性的方式是DSU。所以不放在二分题单里，放在DSU。

多源BFS的大致思路：

1. 选中初始源列表
2. 对于当前轮次的源列表，遍历，访问每个源的所有可行的邻居（在表里并且没被访问过），放到下一轮访问的源列表中
3. 这样就类似于一圈一圈的扩散出去

并查集判连通：由于我们想要的是最大安全系数，所以倒着搜各个安全距离对应的点集。如果发现它的邻居的安全距离大于等于它的，那么可以把它的邻居对应的等级类直接归到这个点对应的等级类。由于我们倒着搜答案，因此这个等价类的门槛会越来越低，直至把所有点都囊括进去，那个时候安全系数也就只能为0了。

import java.util.ArrayList;
import java.util.List;

class Solution {
    static int[][] dirs = new int[][]{
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };
    public int maximumSafenessFactor(List<List<Integer>> grid) {
        // 两个关键问题
        // 怎么标记不能走的格子
        // 怎么判断能否从左上角走到右下角
        int n = grid.size();
        ArrayList<int[]> q = new ArrayList<>(); // 所有为1的网格多源bfs
        int[][] dis = new int[n][n];
        // 统计所有1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(grid.get(i).get(j)==1){
                    q.add(new int[]{i,j});
                }else{
                    dis[i][j] = -1; // 顺便初始化访问数组
                }
            }
        }

        ArrayList<List<int[]>> groups = new ArrayList<>();
        groups.add(q);
        List<int[]> tmp;

        /**
         * 多源bfs的滚动数组trick
         * 相当于一开始现有一个源的列表（多源）
         * 然后每次根据当前的源，访问所有源的所有邻接的邻居 （当前的源就是tmp列表）
         * 把每个邻居放在下一轮源的列表中
         * 由于用tmp接替了q的位置，所以q就变成了下一轮源的列表，这样while(!q.isEmpty())就会判断下一轮是否还有源可以用
         */
        while(!q.isEmpty()){
            tmp = q; // 滚动数组省空间
            q = new ArrayList<>();
            for (int[] p : tmp) {
                for (int[] d : dirs) {
                    int x = p[0]+d[0];
                    int y = p[1]+d[1];
                    // 下标合法并且未访问过（如果访问过，说明它被赋予了更小的值，就没必要更新了）
                    if( x>=0 && x<n && y>=0 && y<n && dis[x][y] == -1){
                        q.add(new int[]{x,y});
                        // 试想如果当前是最初的那一批源会怎么样
                        // groups.size() == 1
                        // 也就意味着当前访问到的邻居距离最初的源的距离为1（这是因为d[0] + d[1]的abs为1，最多能造成1的位移）
                        dis[x][y] = groups.size();
                    }
                }
            }
            groups.add(q); // 最终会多出来一个空的列表
        }

        // 求最大安全系数 所以倒着搜
        // 并查集
        int[] fa = new int[n*n];
        for (int i = 0; i < n * n; i++) {
            fa[i] = i;
        }

        // 由于多源bfs多加了一个数组，倒着搜的时候要-1
        for(int ans = groups.size()-2;ans>0;ans--){
            // 安全距离为ans的点集合
            List<int[]> g = groups.get(ans);
            for (int[] p : g) {
                int i = p[0];
                int j = p[1];

                for (int[] d : dirs) {
                    int x = i+d[0];
                    int y = j+d[1];

                    // 邻居的安全距离大于要判定的安全距离
                    if(x>=0 && x<n && y>=0 && y<n && dis[x][y] >= ans){
                        // 点(x,y)的类 归入到 (i,j)的等价类
                        fa[find(fa,x*n+y)] = find(fa,i*n+j);
                    }
                }
            }
            // 等级类归类完毕查看起点终点是否连通
            if(find(fa,0)==find(fa,n*n-1)){
                return ans;
            }
        }

        return 0;
    }

    // recursive dsu template
    private int find(int[] fa,int x){
        // 如果这个元素的源头不是他自己 说明它被归到别的等价类去了，深搜它的源头（链）
        if(fa[x]!=x) fa[x] = find(fa,fa[x]);
        return fa[x];
    }
}