# Union-Find with no BFS or DFS

• Just traverse the matrix one by one with using recursive method. Union-Find helps it to record connected component. Then, rule out those components touching the boundaries and flip `O` to `X`.

``````class UnionFind():
def __init__(self, m, n):
self.dad = [i for i in xrange(0, m*n)]
self.rank = [0 for i in xrange(0, m*n)]
self.m = m
self.n = n

def find(self, x):

def union(self, xy):
rank = self.rank
x, y = map(self.find, xy)
if x == y:
return False
if rank[x] > rank[y]:
else:
if rank[x] == rank[y]:
rank[y] += 1
return True

class Solution:
def solve(self, board):
if len(board) == 0:
return board
regions = set([])
n, m = len(board), len(board[0])
uf = UnionFind(len(board[0]), len(board))
directions = {"d": (1, 0), "r": (0, 1)}
for i in xrange(0, len(board)):
for j in xrange(0, len(board[0])):
if board[i][j] == 'X':
continue
for d in ["d", "r"]:
di, dj = directions[d]
newi, newj = i + di, j + dj
if newi >= 0 and newi < len(board) and newj >= 0 and newj < len(board[0]):
if board[newi][newj] == "O":
uf.union((newi*m + newj, i*m + j))

for i in xrange(0, len(board)):
for j in [0, len(board[0]) - 1]:
if board[i][j] == "O":

for j in xrange(0, len(board[0])):
for i in [0, len(board) - 1]:
if board[i][j] == "O":