> For the complete documentation index, see [llms.txt](https://liuyang89116.gitbook.io/my-leetcode-book/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuyang89116.gitbook.io/my-leetcode-book/chapter-4-dfs--bfs/problem_200_number_of_islands/problem-305-number-of-islands-ii.md).

# Problem 305: Number of Islands II

> <https://leetcode.com/problems/number-of-islands-ii/#/description>

## ![](https://1241747088-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lpv9LvBSlFaukf_ALqh%2F-Lpv9NPw3Ji1X5Vk8CES%2F-Lpv9xaTpkA9tRejZZwt%2F305_1.png?generation=1569729543879135\&alt=media)![](https://1241747088-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lpv9LvBSlFaukf_ALqh%2F-Lpv9NPw3Ji1X5Vk8CES%2F-Lpv9xaVRC5rLFvuXlh_%2F305_2.png?generation=1569729541933769\&alt=media)

## 思路

> <https://discuss.leetcode.com/topic/29518/java-python-clear-solution-with-unionfind-class-weighting-and-path-compression>

这个答案不错

> <https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf>

Princeton 讲义

* Union Find 经典题目。首先标注一个 2D map 每个 element 的 index ： `index = x * n + y + 1`，这样的话，每个 element 的 index 都是唯一的。
* size (或者 count) 来控制 islands  的个数

## 复杂度

* 时间复杂度：$$O(m \* alpha(n))$$ , $$alpha(n) <= 4$$

```java
public class Solution {
    private int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        UnionFind2D islands = new UnionFind2D(m, n);
        List<Integer> rst = new ArrayList<>();
        for (int[] pos : positions) {
            int x = pos[0], y = pos[1];
            int cur = islands.add(x, y);
            for (int[] d : dir) {
                int next = islands.getId(x + d[0], y + d[1]);
                if (next > 0 && !islands.find(cur, next)) islands.unite(cur, next);
            }
            rst.add(islands.getSize());
        }

        return rst;
    }
}

class UnionFind2D {
    private int[] id;
    private int[] size;
    private int m, n, count;

    public UnionFind2D(int m, int n) {
        this.count = 0;
        this.m = m;
        this.n = n;
        this.id = new int[m * n + 1];
        this.size = new int[m * n + 1];
    }

    public int getIndex(int x, int y) {
        return x * n + y + 1;
    }

    public int getSize() {
        return this.count;
    }

    public int getId(int x, int y) {
        if (x >= 0 && x < m && y >= 0 && y < n) {
            return id[getIndex(x, y)];
        }
        return 0;
    }

    public int add(int x, int y) {
        int index = getIndex(x, y);
        id[index] = index;
        size[index] = 1;
        count++;
        return index;
    }

    public boolean find(int p, int q) {
        return getRoot(p) == getRoot(q);
    }

    public void unite(int p, int q) {
        int i = getRoot(p), j = getRoot(q);
        if (size[i] < size[j]) { // weighted quick union
            id[i] = j;
            size[j] += size[i];
        } else {
            id[j] = i;
            size[i] += size[j];
        }
        count--;
    }

    private int getRoot(int i) {
        while (i != id[i]) {
            i = id[i];           // path compression
            id[i] = id[id[i]];  
        }
        return i;
    }

}
```