Union find 22ms c++

• ``````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;
}
};
``````

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