C++ Union Find Solution


  • 0
    R
    int fa[5050000];
    int Find(int k)
    {
        if(fa[k]==k)return k;
        else return fa[k]=Find(fa[k]);
    }
    
    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            if(grid.size()==0)return 0;
            int ans=0,M=grid.size(),N=grid.at(0).size(),tot_size=M*N;
            memset(fa,-1,sizeof(fa));
            for(int i=0;i<tot_size;i++)
                if(grid.at(i/N).at(i%N)=='1')fa[i]=i;
            for(int i=0;i<tot_size;i++)
            {
                int x=i/N,y=i%N;
                if(grid.at(x).at(y)=='0')continue;
                if(x>0&&grid.at(x-1).at(y)=='1')fa[Find(i-N)]=Find(i);
                if(y>0&&grid.at(x).at(y-1)=='1')fa[Find(i-1)]=Find(i);
                if(x<M-1&&grid.at(x+1).at(y)=='1')fa[Find(i+N)]=Find(i);
                if(y<N-1&&grid.at(x).at(y+1)=='1')fa[Find(i+1)]=Find(i);
            }
            for(int i=0;i<tot_size;i++)
                if(fa[i]==i)ans++;
            return ans;
        }
    };
    

Log in to reply
 

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