CS61B - UnionFind & BubbleGrid

UnionFind（并查集）

sp19的lab6，18是没有的。要求是自己实现一遍UnionFind，然后做一个应用。

此处实现的是WeightUnionFind，按照树的weight决定连接优先级。在find方法里，包括了path compression。

public class UnionFind {

    private int[] parent;

    /** Creates a UnionFind data structure holding n vertices.
     * Initially, all vertices are in disjoint sets.
     */
    public UnionFind(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("It must be positive!");
        }
        parent =  new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = -1;
        }
    }

    /** Throws an exception if v1 is not a valid index. */
    public void validate(int v1) {
        if (!(v1 >= 0 && v1 < parent.length)) {
            throw new RuntimeException(v1 + " is not a valid index.");
        }
    }

    /** Returns the size of the set v1 belongs to. */
    public int sizeOf(int v1) {
        return -parent[find(v1)];
    }

    /** Returns the parent of v1.
     * If v1 is the root of a tree, returns the negative size of the tree for which v1 is the root.
     */
    public int parent(int v1) {
        return parent[v1];
    }

    /** Find the root of v. */
    public int find(int v) {
        int r = v;
        int temp;

        while (parent[r] >= 0) {
            r = parent[r];
        }
        // Path compression.
        while (parent[v] >= 0) {
            temp = parent[v];
            parent[v] = r;
            v = temp;
        }
        return r;
    }

    /** Returns true if nodes v1 and v2 are connected. */
    public boolean connected(int v1, int v2) {
        return find(v1) == find(v2);
    }

    /** Connects two elements v1 and v2 together.
     * v1 and v2 can be any valid elements, and a union-by-size heuristic is used.
     * If the sizes of the sets are equal, tie break by connecting v1’s root to v2’s root.
     * Unioning a vertex with itself or vertices that are already connected should not change the sets,
     * but it may alter the internal structure of the data structure.
     */
    public void union(int v1, int v2) {
        if (!connected(v1, v2)) {
            int r1 = find(v1);
            int r2 = find(v2);
            int size1 = -parent[r1];
            int size2 = -parent[r2];

            if (size1 >= size2) {
                parent[r2] = r1;
                parent[r1] = -(size1 + size2);
            } else {
                parent[r1] = r2;
                parent[r2] = -(size1 + size2);
            }
        }
    }

}

BubbleGrid

sp19 - clab6

要求如下：

• 首先给出一个二维数组，下标代表坐标，值只有0或1，1代表该处有一个泡泡，0为空。
• 初始状态，所有泡泡都是“被黏住”的。黏住的定义是：泡泡在最顶层（也就是grid[0]上），或者泡泡的主方向上存在被黏住的泡泡。（学了个新词，orthogonally adjacent to，意思是主方向相邻）。
• 然后，向grid中的位置扔darts。darts也是二维数组，darts[i]代表第i个dart，里面存储了该dart的位置。
• 如果dart所及位置是0，则没有任何改变；如果是1，则代表该处泡泡被"pop"，变为0，需要统计此时，有多少泡泡失去连接掉下来。返回一个数组存储了每次扔飞镖时掉落的泡泡。

举个例子：

此题是Leetcode上一道hard题，经典的并查集应用。搞着搞着发现很难，原来是hard。。
Leetcode 803 - 打砖块
下面上代码，注释写的很详细了。思路是逆向思维，先把所有飞镖射中的地方变成0，然后逐个变成1，倒着统计每次增加1时，增加的与顶部相连的泡泡数量。比较tricky的一点是，另外建立一个节点C * R，与顶部所有的1相连，这样只需sizeOf(C *R)就可以得到与顶部相连的泡泡数量。

public class BubbleGrid {
    
    private int[][] grid;
    private UnionFind unionGrid;
    private int R;
    private int C;
    private int[] dx = {-1, 1, 0, 0};
    private int[] dy = {0, 0, -1, 1};

    /** 两个helper方法 */
    private int cvt2dArray(int row, int col) {
        return row * C + col;
    }
    /* 连接主方向上四个点 */
    private void orthogonallyUnion(int[][] grid, int row, int col) {
        for (int i = 0; i < 4; i++) {
            if ((row + dx[i] >= 0 && row + dx[i] < R) && (col + dy[i] >= 0 && col + dy[i] < C)) { //保证不超出grid范围
                if (grid[row + dx[i]][col + dy[i]] == 1) { //如果主方向某点是1，才连接
                    unionGrid.union(cvt2dArray(row, col), cvt2dArray(row + dx[i], col + dy[i]));
                }
            }
        }
    }
    
    /** 在去掉所有darts点后，初始化UnionFind，遍历所有grid */
    private void gridToUnionFind(int[][] grid) {
        for (int row = 0; row < R; row++) {
            for (int col = 0; col < C; col++) {
                if (grid[row][col] == 1) {
                    if (row == 0) {
                        unionGrid.union(R * C, col);
                    } else {
                        orthogonallyUnion(grid, row, col); //其实不用连接四个方向
                    }
                }
            }
        }
    }

    /** 构造函数，把grid的长宽保存，方便一点 */
    public BubbleGrid(int[][] grid) {
        this.grid = grid;
        R = grid.length;
        C = grid[0].length;
        unionGrid = new UnionFind(R * C + 1); //单独建一个R * C节点，所有的顶部泡泡都与他相连，方便统计
    }

    /**
     * @param darts: darts is an array of 2-element arrays representing the grid positions
     * (in [row, column] format) at which darts are thrown in sequence
     * (i.e. a dart is thrown at position darts[t] at time t).
     * You may assume all elements of darts are unique, valid positions within the grid.
     * @return: an array where the i-th element is the number of bubbles that fall
     * after the i-th dart is thrown (popped bubbles do not fall!).
     */
    public int[] popBubbles(int[][] darts) {
        int[] count = new int[darts.length];
        int[][] gridCopy = new int[R][C];

        // 拷贝一个新数组，把pop的泡泡变0, 初始化UnionFind
        for (int i = 0; i < R; i++) {
            gridCopy[i] = grid[i].clone();
        }
        for (int[] dart: darts) {
            gridCopy[dart[0]][dart[1]] = 0;
        }
        gridToUnionFind(gridCopy);
        // 初始与顶部相连的泡泡数量
        int connectToCeiling = unionGrid.sizeOf(R * C);

        // 每加一个泡泡，统计增加了多少泡泡与顶部相连
        for (int i = darts.length - 1; i >= 0; i--) {
            int r = darts[i][0];
            int c = darts[i][1];
            if (grid[r][c] != 0) { //如果dart之前也没有泡泡，dart就没用，count = 0；如果有，就将该点设为1
                gridCopy[r][c] = 1;
                if (r == 0) { //如果该点是顶部，还要与R * C相连
                    unionGrid.union(R * C, cvt2dArray(r, c));
                }
                orthogonallyUnion(gridCopy, r, c); //与该点主方向四个点相连
                int cur = unionGrid.sizeOf(R * C); //计算现在与顶部相连的泡泡数量
                int inc = cur - connectToCeiling; //计算增加的与顶部相连的泡泡数量
                if (inc != 0) { //不算pop的泡泡
                    count[i] = inc - 1;
                } else {
                    count[i] = 0;
                }
                connectToCeiling = cur; //更新
            } else {
                count[i] = 0;
            }
        }
        return count;
    }
}

逆向考虑时，只需要一个UnionFind instance，因为每次操作是要额外union操作。然而正向考虑时， 会发现无法用一个instance实现，因为需要的是disunion，对于weightUnionFind无法实现这个方法（不是将每个节点相连，而是将root相连），只能每次新建一个UnionFind，重新扫描全部grid，并且判断一个位置是否与顶部相连也很麻烦，因为顶部不一定是root。总之正向考虑复杂度很高，我开始先实现了正向，最后leetcode上测试时间超出限制。