200. Number of Islands

https://leetcode.com/problems/number-of-islands/description/

Given a 2d grid map of'1's (land) and '0's (water), count the number of islands. 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.

Thoughts

01矩阵中的1和上下左右的其余1会合并成一个集合，问给定的矩阵最后有几个的集合。 集合合并，并查集的典型应用。

Code

/*
 * @lc app=leetcode id=200 lang=cpp
 *
 * [200] Number of Islands
 */

// @lc code=start
class Solution {
class UF {
public:
    vector<int> parent;
    int size = 0;
    UF(const int N): parent(N) {
        for (int i = 0; i < N; ++i) {
            parent[i] = i;
        }
    }
    void un(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            parent[x] = y;
            --size;
        }
    }
    int find(int x) {
        while (x != parent[x]) {
            x = parent[x];
            parent[x] = parent[parent[x]];
        }
        return x;
    }
};
public:
    int numIslands(vector<vector<char>>& grid) {
        const int M = grid.size(), N = M == 0 ? 0 : grid[0].size();
        UF uf(M * N);
        vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == '0') continue;
                ++uf.size;
                for (const auto &d : dirs) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && x < M && y >= 0 && y < N && grid[x][y] == '1') {
                        uf.un(i * N + j, x * N + y);
                    }
                }
            }
        } 
        return uf.size;      
    }
};
// @lc code=end

class Solution {
    class UnionFind {
        int[] father;
        int size;

        UnionFind(int n) {
            father = new int[n];
        }

        void union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                size--;
                father[x] = y;
            }
        }

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

    int[][] dirs = new int[][]{{-1, 0}, {0, -1}};
    public int numIslands(char[][] grid) {
        int m = grid.length, n = m == 0 ? 0 : grid[0].length;
        UnionFind uf = new UnionFind(m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    uf.father[i * n + j] = i * n + j;
                    uf.size++;
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                            uf.union(i * n + j, x * n + y);
                        }
                    }
                }
            }
        }

        return uf.size;
    }
}

Analysis

http://bgmeow.xyz/2017/01/07/union-find/

不带路径压缩是每次uf.find操作为O(mn), 一共O(m^2n^2).