Solution using disjoint sets


#1

vector<vector> rak;
vector<vector<pair<int,int>>> par;
int sts;

void create_set(int n,int m)
{
rak.resize(n,vector(m,0));
par.resize(n,vector<pair<int,int>>(m,{0,0}));

for(int i=0;i<n;i++)
{
    for(int j=0;j<m;j++)
    {
        par[i][j]={i,j};
    }
}

}
pair<int,int> find_set(pair<int,int> a)
{
if(a!=par[a.first][a.second])
par[a.first][a.second]=find_set(par[a.first][a.second]);

return par[a.first][a.second];

}

void merge_set(pair<int,int> a,pair<int,int> b)
{
a=find_set(a);
b=find_set(b);

if(rak[a.first][a.second]>rak[b.first][b.second])
    par[b.first][b.second]=a;
else
    par[a.first][a.second]=b;
    
if(rak[a.first][a.first]==rak[b.first][b.first])
    rak[b.first][b.second]++;
sts--;

}

int Solution::black(vector &A) {

rak.clear();
par.clear();
sts=0;

int n=A.size(),m=A[0].size();

create_set(n,m);
sts=n*m;
//cout<<sts<<endl;
for(int i=0;i<n;i++)
{
    for(int j=0;j<m;j++)
    {
        if(A[i][j]=='O')
        {
            sts--;
            continue;
        }
        if(i>0&&A[i-1][j]=='X')
        {
            if(find_set({i,j})!=find_set({i-1,j}))
                merge_set({i,j},{i-1,j});
        }
        if(j>0&&A[i][j-1]=='X')
        {
            if(find_set({i,j})!=find_set({i,j-1}))
                merge_set({i,j},{i,j-1});
        }
    }
}

//cout<<sts<<endl;
return sts;

}