The game of Hex is played on an n n board composed of hexagonal cells. Two players take turns 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. Formalize 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.

blac OKO O O bla Figure 1: An illustration of a Hex game in progress, with n 11 5. [10 pts] The game of Hex is played on an n x n board composed of hexagonal cells. Two players take turns 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. Formalize 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