c++ union find solution


  • 1
    H
    class Solution {
    public:
        vector<int> parent;
        vector<int> size;
        void init(vector<int> &parent, vector<int> &size, int m, int n) {
            for(int i = 0; i < m; i ++) {
                for(int j = 0; j < n; j ++) {
                    parent.push_back(i*n + j);
                    size.push_back(1);
                }
            }
        }
        int findParent(int a) {
            if(parent[a] == a) return a;
            parent[a] = findParent(parent[a]);
            return parent[a];
        }
        void linkBySize(int a, int b) {
            int pa = findParent(a);
            int pb = findParent(b);
            if(pa == pb) return;
            if(size[pa] >= size[pb]) {
                size[pa] += size[pb];
                parent[pb] = pa;
            }
            else {
                size[pb] += size[pa];
                parent[pa] = pb;
            }
        }
        int numIslands(vector<vector<char>>& grid) {
            int m = grid.size();
            if(!m) return 0;
            int n = grid[0].size();
            init(parent, size, m, n);
            for(int i = 0; i < m; i ++) {
                for(int j = 0; j < n; j ++) {
                    if(grid[i][j] == '1') {
                        int i_down = min(i+1, m-1);
                        int j_right = min(j+1, n-1);
                        if(grid[i][j_right] == '1') linkBySize(i*n + j, i*n + j_right);
                        if(grid[i_down][j] == '1') linkBySize(i*n + j, i_down*n + j);
                    }
                }
            }
            int cnt = 0;
            for(int i = 0; i < m; i ++) {
                for(int j = 0; j < n; j ++) {
                    if(grid[i][j] == '1' && parent[i*n+j] == i*n+j) {
                        cnt ++;
                    }
                }
            }
            return cnt;
        }
    };
    

Log in to reply
 

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