# A more concise solution with Union-Find Set

• ``````class Solution {
public:
vector<int> pa;

int find(int n) {
return pa[n] == n ? n : pa[n] = find(pa[n]);
}

void unite(int n1, int n2) {
int p1 = find(n1);
int p2 = find(n2);
if (p1 == pa.size()-1) {
pa[p2] = p1;
} else {
pa[p1] = p2;
}
}

void solve(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) {
return ;
}
pa.resize(board.size() * board[0].size()+1);
for (int i = 0; i < pa.size(); ++i) {
pa[i] = i;
}
for (int y = 0; y < board.size(); ++y) {
for (int x = 0; x < board[y].size(); ++x) {
if (board[y][x] == 'X') {
continue;
}
if (x == 0 || y == 0 || y+1 == board.size() || x+1 == board[y].size()) {
unite(pa.size()-1, y*board[0].size()+x);
}
if (x > 0 && board[y][x-1] == 'O') {
unite(y*board[0].size()+x-1, y*board[0].size()+x);
}
if (y > 0 && board[y-1][x] == 'O') {
unite((y-1)*board[0].size()+x, y*board[0].size()+x);
}
}
}
for (int y = 0; y < board.size(); ++y) {
for (int x = 0; x < board[y].size(); ++x) {
if (board[y][x] == 'O' && find(y*board[0].size()+x) != pa.size()-1) {
board[y][x] = 'X';
}
}
}
}
};
``````

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