Number of Island II

Question

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Solution

這題是 Number of Island 的 follow-up，基本上這種給圖找連結的題目，都可以用 Union-Find 來實現。在 Number of Island 那題，用 DFS 是一個非常直觀的算法。但在這題，帶進 UF 的方法會比較好做。需要注意的地方：

1. linear mapping：n * X + Y (這個套用在所有 2d 轉 1d 的情況)
2. 在同個 island 裡會有不同的 roots[node]，因為 roots[node] 只記錄當前這個 node 的 parent。為了找到最終的 parent，要特別寫一個 findIsIand 來實現

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

public List<Integer> numIslands2(int m, int n, int[][] positions) {
    List<Integer> result = new ArrayList<>();
    if(m <= 0 || n <= 0) return result;

    int count = 0;                      // number of islands
    int[] roots = new int[m * n];       // one island = one tree
    Arrays.fill(roots, -1);            

    for(int[] p : positions) {
        int root = n * p[0] + p[1];     // assume new point is isolated island
        roots[root] = root;             // add new island
        count++;

        for(int[] dir : dirs) {
            int x = p[0] + dir[0]; 
            int y = p[1] + dir[1];
            int nb = n * x + y;
            if(x < 0 || x >= m || y < 0 || y >= n || roots[nb] == -1) continue;

            int rootNb = findIsland(roots, nb);
            if(root != rootNb) {        // if neighbor is in another island
                roots[root] = rootNb;   // union two islands 
                root = rootNb;          // current tree root = joined tree root
                count--;               
            }
        }

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

public int findIsland(int[] roots, int id) {
    while(id != roots[id]) id = roots[id];
    return id;
}

Bonus

Path Compression 只要在 findIsland 裡面加入這行就可以把樹高度壓縮，讓程式效率更好

roots[id] = roots[roots[id]];