My C++ solution using Union - Find Set


  • 2
    G
    class Solution {
    public:
        int total;
        int getparent(vector<int>& parent,int a){
            if(parent[a] != a)
                parent[a] = getparent(parent,parent[a]);
            return parent[a];
        }
        void merge(vector<int>& parent,int a,int b){
            int p1 = getparent(parent,a);
            int p2 = getparent(parent,b);
            if(p1 == p2)  return;
            parent[p2] = p1;
            --total; 
        }
        int numIslands(vector<vector<char>>& grid) {
            if(grid.size() == 0 || grid[0].size() == 0) return 0;
            int M = grid.size();
            int N = grid[0].size();
            vector<int> parent(M*N);
            total = M*N;
            for(int i=0;i<M;++i)
                for(int j=0;j<N;++j){
                    int index = i*N+j;
                    parent[index] = index;
                    if(grid[i][j] == '0') --total;
                    else{
                        if(i>0 && grid[i-1][j] == '1')
                            merge(parent,index,(i-1)*N + j);
                        if(j>0 && grid[i][j-1] == '1')
                            merge(parent,index,index-1);
                    }
                }
            return total;
        }
    };

  • 0
    T

    Clean code!Can you please explain this a little bit? thanks!


  • 0
    T

    Oh never mind I think I got it. nice!


Log in to reply
 

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