C++ solution with Union find class


  • 3
    C

    class Union{

    public:

    vector<int>parent;
    vector<int>size;
    int cou ;
    Union(int n){
        parent =vector<int>(n);
        size = vector<int>(n,1);
        for(int i =0;i< n;i++)
            parent[i] = i;
        cou = n;
    }
    
    int count(){
        return cou;
    }
    
    void connect(int a,int b){
        int aa = find(a);
        int bb = find(b);
        if(aa ==bb)
            return ;
        
        if(size[aa] <= size[bb]){
            size[bb] +=size[aa];
            parent[aa] = bb;
            
        }else{
            size[aa] +=size[bb];
            parent[bb] = aa;
        }
        
        cou --;
    }
    
    bool isConnect(int a,int b){
        return find(a) == find (b);
    }
    
    int find(int m){
        if(parent[m] == m)
            return m;
        
        parent[m] = find(parent[m]);
        
        return parent[m];
    }
    

    };

    class Solution {
    public:

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m==0)
            return 0;
        int n = grid[0].size();
        Union u = Union(m*n);
        int first = false;
        int is = 0;
        for(int i =0;i<m;i++){
            for(int j =0;j<n ;j++){
                int tmp = n*i +j;
                if(grid[i][j] == '1'){
                    if(i+1 < m && grid[i+1][j] == '1')
                        u.connect(tmp,(i+1)*n+j);
                    if(i-1 >=0 && grid[i-1][j] == '1')
                        u.connect(tmp,(i-1)*n+j);
                    if(j+1 < n && grid[i][j+1] == '1')
                        u.connect(tmp,(i)*n+j+1);
                    if(j-1 >=0 && grid[i][j-1] == '1')
                        u.connect(tmp,(i)*n+j-1);
                }else{
                    if(first == false){
                        is = i *n +j;
                        first =true;
                    }else{
                        u.connect(is,i*n+j);
                    }
                }
            }
        }
        
        
        return u.count() - first;
    }
    

    };


Log in to reply
 

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