public List<Integer> numIslands2(int m, int n, int[][] positions) {

    int[] rootArray = new int[m*n];

    Arrays.fill(rootArray,-1);

    ArrayList<Integer> result = new ArrayList<Integer>();

    int[][] directions = {{-1,0},{0,1},{1,0},{0,-1}};

    int count=0;

    for(int k=0; k<positions.length; k++){

        count++;

        int[] p = positions[k];

        int index = p[0]*n+p[1];

        rootArray[index]=index;//set root to be itself for each node

        for(int r=0;r<4;r++){

            int i=p[0]+directions[r][0];

            int j=p[1]+directions[r][1];

            if(i>=0&&j>=0&&i<m&&j<n&&rootArray[i*n+j]!=-1){

                //get neighbor's root

                int thisRoot = getRoot(rootArray, i*n+j);

                if(thisRoot!=index){

                    rootArray[thisRoot]=index;//set previous root's root

                    count--;

                }

            }

        }

        result.add(count);

    }

    return result;

}

public int getRoot(int[] arr, int i){

    while(i!=arr[i]){

        i=arr[i];

    }

    return i;

}

public class Solution {

    public List<Integer> numIslands2(int m, int n, int[][] positions) {

        int[] id = new int[m * n]; // 表示各个index对应的root

        List<Integer> res = new ArrayList<>();

        Arrays.fill(id, -1); // 初始化root为-1，用来标记water, 非-1表示land

        int count = 0; // 记录island的数量

        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        for (int i = 0; i < positions.length; i++) {

            count++;

            int index = positions[i][0] * n + positions[i][1];

            id[index] = index; // root初始化

            for (int j = 0; j < dirs.length; j++) {

                int x = positions[i][0] + dirs[j][0];

                int y = positions[i][1] + dirs[j][1];

                if (x >= 0 && x < m && y >= 0 && y < n && id[x * n + y] != -1) {

                    int root = root(id, x * n + y);

                    // 发现root不等的情况下，才union, 同时减小count

                    if (root != index) {

                        id[root] = index;

                        count--;

                    }

                }

            }

            res.add(count);

        }

        return res;

    }

    public int root(int[] id, int i) {

        while (i != id[i]) {

            id[i] = id[id[i]]; // 优化，为了减小树的高度

            i = id[i];

        }

        return i;

    }

}