# Share my C++ Union-Find solution, which is self-explanatory.

• The Union Find implementation uses union by rank and path compression. All we need is to find all 'O's in the boundary and union all adjacent 'O's.

``````class Unions {
private:
vector<int> roots;
vector<int> ranks;
public:
Unions(int m, int n) {
int size = m*n;
roots.resize(size);
ranks.resize(size);
for (int i=0; i<size; ++i) {
roots[i] = i;
ranks[i] = 0;
}
}

int findRoot (int x) {
if (x != roots[x]) {
roots[x] = findRoot(roots[x]);
}
return roots[x];
}

void unionAll(int x, int y) {
int rootX = findRoot(x);
int rootY = findRoot(y);

if (ranks[rootX] > ranks[rootY]) {
roots[rootY] = rootX;
} else {
roots[rootX] = rootY;
if (ranks[rootX] == ranks[rootY]) {
++ranks[rootY];
}
}
}
};

class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return;
int m = board.size();
int n = board[0].size();
Unions unions(m, n);
int boundary = -1;
int cur;
for (int i=0; i<m; ++i) {
for (int j=0; j<n; ++j) {
if (board[i][j] == 'O') {
cur = i*n+j;
if (inBoundary(i, j, m, n)) {
if (boundary != -1) {
unions.unionAll(boundary, cur);
} else {
boundary = cur;
}
}
if (i+1<m && board[i+1][j] == 'O') {
unions.unionAll(cur, (i+1)*n+j);
}
if (j+1<n && board[i][j+1] == 'O') {
unions.unionAll(cur, i*n+j+1);
}
}
}
}

if (boundary == -1) {
for (auto &aLine : board) {
for (auto &c: aLine) {
c = 'X';
}
}
return;
}

int boundaryRoot = unions.findRoot(boundary);
for (int i=0; i<m; ++i) {
for (int j=0; j<n; ++j) {
if (unions.findRoot(i*n+j) != boundaryRoot) {
board[i][j] = 'X';
}
}
}

}

inline bool inBoundary(int x, int y, int m, int n) {
return (x==0 || y==0 || x==m-1 || y==n-1);
}
};``````

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