The game of Hex is played on an n times n board composed of

The game of Hex is played on an n times n board composed of hexagonal cells. Two players take placing black and white stones on the cells (see figure 1 for an illustration of a hex game in progress). If the upper left and lower right sides are connected to each other by a path of black stones, the black player wins. If the lower left and upper right sides are connected to each other by a path of white stones, the white player wins. Formalizer the problem of detecting when one of the players has won and show how union-find can help with this problem. Provide some details as to the resulting running-time of your approach.

Solution

function Find(p)
if p.parentRoot != p
p.parentRoot := Find(p.parentRoot)
return p.parentRoot

function Union(p, q)
xRoot := Find(p)
yRoot := Find(q)

// if both values are in same set
if xRoot == yRoot
return

// if both p and q are not in same set, we need to merge them
if xRoot.rank < yRoot.rank
xRoot.parentRoot := yRoot
else if xRoot.rank > yRoot.rank
yRoot.parentRoot := xRoot
else
//make new parentRoot to be one root
yRoot.parentRoot := xRoot
xRoot.rank := xRoot.rank + 1

----------------------------------------------------------------------------------------------------------------------------
Idea behind this find-union method to solve hex game is..
When new piece is placed, then it gives new equivalence class. Then its neighbours of same
colors need to merge. Also each edge on board will have different color virtual stones.
So if edge stone having same color will oppose virtual edge stones, then connection will made and finish the game.

--------------------------------------------------------------------------------------
Coming to complexity of this algorithm is..
As find method takes O(n) time since it needs to traverse entire tree height in worst case.
So combinely union-find algorithm will takes O(n) running time complexity.