number of islands ii:

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int[][] grid = new int[m][n];
        int[] dx = new int[] {0,1,0,-1};
        int[] dy = new int[] {-1,0,1,0};
        List<Integer> rst = new ArrayList<>();
        int count = 0;

        UnionFind uf = new UnionFind(m*n);

        for (int[] position : positions) {
            int x = position[0];
            int y = position[1];
            int id = convert2Id(x, y, n);

            if (grid[x][y] != 1) {
                grid[x][y] = 1;
                count++;  
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    int neighborId = convert2Id(nx, ny, n);
                    if (nx > m-1 || nx < 0 || ny > n-1 || ny < 0) continue;
                    if (grid[nx][ny] == 0) continue;
                    if (uf.find(id) != uf.find(neighborId)) {    // to avoid dup -- 
                        count--;
                        uf.union(neighborId, id);
                    }
                }

            }
            rst.add(count);                    
        }
        return rst;        
    }

    private int convert2Id(int x, int y, int col) {
        return x*col+y;
    }

    class UnionFind {
        int[] father;
        UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i< n; i++) {
                father[i] = i;
            }
        }

        int find(int x) {
            if (x == father[x]) return x;
            return father[x] = find(father[x]);
        }

        void union(int a, int b) {
            int A = find(a);
            int B = find(b);
            if (A != B) {
                father[B] = A;
            }
        }
    }
}

surrounded regions

public class Solution {
    public void surroundedRegions(char[][] board) {
        // write your code here
        int rows = board.length;
        if (rows == 0) return;
        int cols = board[0].length;
        if (cols == 0) return;
        UnionFind uf = new UnionFind(cols * rows + 1); // one more dummy node

        int[] dx = new int[] {1,0,-1,0};
        int[] dy = new int[] {0,1,0,-1};

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int id = convert2Id(i, j, cols);
                int dummy = rows*cols;
                if (board[i][j] == 'O') {
                    if (i==0 || i==rows-1 || j==0 || j==cols-1) uf.union(dummy, id);
                    else {
                        for (int k = 0; k < 4; k++) {
                            int x = i + dx[k];
                            int y = j + dy[k];
                            int nid = convert2Id(x, y, cols);
                            if (board[x][y] == 'O') uf.union(id, nid);
                        }    
                    }
                }
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int id = convert2Id(i, j, cols);
                if (uf.find(id) != uf.find(cols*rows)) board[i][j] = 'X';
            }
        }
    }

    private int convert2Id(int x, int y, int col) {
        return x*col+y;
    }
}