Union find 22ms c++


  • 0
    E
    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            if(board.size()<1)return;
            int r=board.size(),c=board[0].size();
            vector<int>sz(r*c+1,1),idx(r*c+1,1); //sz[i] is the size of 'Union' i
            for(int i=0;i<r;i++){ //idx[i] is the 'Union id' of i, if i is edge, id<0
                for(int j=0;j<c;j++){
                    if((i==0||i==r-1||j==0||j==c-1)&&board[i][j]=='O')idx[j+i*c+1]=-j-i*c-1;
                    else idx[j+i*c+1]=j+i*c+1;}
            }
            for(int i=0;i<r;i++){//for1
                for(int j=0;j<c;j++){//for2
                    if(board[i][j]=='X')continue;
                    int it=find(j+i*c+1,idx); //get the 'Union id' of 'j+i*c+1'
                    int off[2][2]={{1,0},{0,1}};
                    for(int k=0;k<2;k++){//for3, visit the right and the below
                        int x=i+off[k][0],y=j+off[k][1];
                        if(x<r&&y<c&&board[x][y]=='O'){//if2
                            int jt=find(y+x*c+1,idx); //get the 'Union id' of 'y+x*c+1'
                            if(it==jt)continue;
                            if(sz[it]<sz[jt]){ //merge unions
                                if(idx[it]<0&&idx[jt]>0)idx[jt]*=-1; //make sure the Union id of edge union is negtive
                                idx[it]=jt;sz[jt]+=sz[it];
                            }else{
                                if(idx[jt]<0&&idx[it]>0)idx[it]*=-1;
                                idx[jt]=it;sz[it]+=sz[jt];
                            }
                        }//if2
                    }//for3
                }//for2
            }//for1
            for(int i=0;i<r;i++){ //change char
                for(int j=0;j<c;j++){
                    if(board[i][j]=='O'){
                        int id=j+i*c+1;
                        while(id!=abs(idx[id]))id=abs(idx[id]);
                        if(idx[id]>0)board[i][j]='X';
                    }
                }
            }
        }
        int find(int i,vector<int>&idx){
            while(i!=abs(idx[i])){
                idx[i]=idx[abs(idx[i])];        
                i=abs(idx[i]);
            }
            return i;
        }
    };
    

Log in to reply
 

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