Accepted C++ union find solution


  • 1
    T

    Borrowed idea from here(https://leetcode.com/discuss/48444/my-c-solution-using-union-find-set). Added some comments.

    class Solution {
        public:
            int total;
            int find(vector<int> & parents, int index) {
                if(parents[index]==-1)return index;
                return find(parents, parents[index]);
            }
            void merge(vector<int> & parents, int a, int b){
                int parent_a = find(parents, a);
                int parent_b = find(parents, b);
                if(parent_a!=parent_b){
                    parents[parent_b]=parent_a;//set the new 's parent to be old one.
                    total--;
                }
            }
            int numIslands(vector<vector<char>>& grid) {
                int rows = grid.size();
                if (rows==0) return 0;
                int cols = grid[0].size();
                vector<int>parents(rows*cols,-1);//use array at first all initialized as -1;
                total=rows*cols; // we start with m*n sets and will reduce them
                for(int i=0;i<rows;i++){
                    for(int j=0;j<cols;j++){
                        if(grid[i][j]=='0') total--;
                        //now all 1s
                        else{
                            int index = i*cols+j;
                            //we only need to consider those we have visited and merge with them, so only two neighbers are considered.
                            //the neigher needs to be '1'.
                            if(i>0 && grid[i-1][j]=='1'){
                                merge(parents, (i-1)*cols+j, index);
                            }
                            if(j>0 && grid[i][j-1]=='1'){
                                merge(parents, i*cols+j-1, index);
                            }
                        }
                    }
                }
                return total;
            }
            
        };

Log in to reply
 

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