Not DFS nor BFS, but Disjoint Set in C++. 10ms solution


  • 0
    F

    I solved it in two ways, one is BFS, the other is Disjoint Set.

    //Solution 2: 并查集
    //            Disjoint set
    //            time: O(n)
    //            space: O(n)
    //            10ms
    class Solution {
    public:
        int nr_row, nr_col;
        const int TYPE_WATER = 0x7fffffff;
        int numIslands(vector<vector<char> > &grid) {
            if (grid.empty() || grid[0].empty()) {
                return 0;
            }
            nr_row = grid.size();
            nr_col = grid[0].size();
    
            int type_num = 0;
            vector<int> type(nr_col + 1, TYPE_WATER); //type[k+1] => grid[x][k] type
            unordered_map<int, int> table;            //并查集, disjoint set
            for (int i = 0; i < nr_row; ++i) {
                for (int j = 0; j < nr_col; ++j) {
                    int near_type = min(type[j], type[j+1]);
                    if (grid[i][j] == '1') {
                        if (type[j] != TYPE_WATER && type[j+1] != TYPE_WATER) {
                            int group1 = find_parent(table, type[j]);
                            int group2 = find_parent(table, type[j+1]);
                            table[max(group1, group2)] = min(group1, group2);
                        }
                        if (near_type == TYPE_WATER) {
                            type[j+1] = ++type_num;
                            table[type[j+1]] = type[j+1];
                        } else {
                            type[j+1] = near_type;
                        }
                    } else {
                        type[j+1] = TYPE_WATER;
                    }
                }
            }
    
            unordered_set<int> s;
            for (int i = 1; i <= type_num; ++i) {
                s.insert(find_parent(table, i));
            }
            return s.size();
        }
    
        int find_parent(unordered_map<int, int> &table, int type) {
            return table[type] == type ? type :
                    table[type] = find_parent(table, table[type]);
        }
    };
    

    And below is the normal BFS one:

    //Solution 1: BFS广度优先遍历
    //            Breadth-First Search
    //            time: O(n)
    //            space: < O(n)
    //            14ms
    class Solution {
    public:
        struct Point {
            int row, col;
            Point(int _x, int _y) : row(_x), col(_y) {}
        };
        int nr_row, nr_col;
        int numIslands(vector<vector<char> > &grid) {
            if (grid.empty() || grid[0].empty()) {
                return 0;
            }
    
            nr_row = grid.size();
            nr_col = grid[0].size();
    
            int res = 0;
            queue<Point> q;
            
            for (int i = 0; i < nr_row; ++i) {
                for (int j = 0; j < nr_col; ++j) {
                    if (grid[i][j] == '0') {
                        continue;
                    }
                    ++res;
    
                    grid[i][j] = '0';
                    q.push(Point(i, j));
                    while (!q.empty()) {
                        Point point = q.front();
                        q.pop();
                        addNeighbor(grid, point, -1,  0, q);
                        addNeighbor(grid, point,  0, -1, q);
                        addNeighbor(grid, point,  1,  0, q);
                        addNeighbor(grid, point,  0,  1, q);
                    }
                }
            }
            return res;
        }
    
        void addNeighbor(vector<vector<char> > &grid, Point point, 
                int d_row, int d_col, queue<Point> &q) {
            point.row += d_row;
            point.col += d_col;
            if (point.row >= nr_row || point.col >= nr_col || 
                    point.row < 0 || point.col < 0 ||
                    grid[point.row][point.col] == '0') {
                return;
            }
            grid[point.row][point.col] = '0';
    
            q.push(point);
        }
    };
    

    Feel free to visit: https://github.com/fanfank/leetcode


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.