title: Weighted Quick Union
body: <p>I am currently doing Algorithms in collage and we are asked to make a hex game using Weighted quick union, we were given most of the code for the project by the lecturer. But im running into a problem here.`public class Hex implements BoardGame {</p>
  
  <pre><code>private int[][] board; // 2D Board. 0 - empty, 1 - Player 1, 2 - Player 2 
  
  private int n1, n2; // height and width of board
  
  private WeightedQuickUnionUF wqu; // Union Find data structure to keep track
                                      // of unions and calculate winner
  
  private int currentPlayer; // Current player in the game, initialised to 1
  
  public Hex(int n1, int n2) // create N-by-N grid, with all sites blocked
  {
      this.n1 = n1;
      this.n2 = n2;
      currentPlayer = 1;
  
      // TODO: Create instance of board
      // TODO: Create instance WeightedQuickUnionUF class
      wqu = new WeightedQuickUnionUF(14);
      board = new int[n1][n2];
  
      for(int i=0; i &lt; n1 ; i++){
          for(int j = 0; j &lt; n2; j++){
              board[i][j] = 0;
  
          }
      }
  }
  
  /*
   * (non-Javadoc)
   * 
   * @see BoardGame#takeTurn(int, int)
   */
  @Override
  public void takeTurn(int x, int y) {
  
      if(((x &gt; n1) || (x &lt; 0)) || ((y &gt; n2) || (y &lt; 0)))
      {
          StdOut.println("Wrong");
      } 
      else{
  
          if(board[x][y] == 0){
              board[x][y] = currentPlayer;
          }
          else{
              StdOut.println("Taken");
          }
  
      }
  
  
      // TODO: check coords are valid
      // TODO: check if location is free and set to player's value(1 or 2).
  
      // TODO: calculate location and neighbours location in
      // WeightedQuickUnionUF data structure
  
      // TODO: create unions to neighbour sites in WeightedQuickUnionUF that
      // also contain current players value
  
      // TODO: if no winner get the next player
  
  }
  
  
  
  /*
   * (non-Javadoc)
   * 
   * @see BoardGame#getCurrentPlayer()
   */
  @Override
  public int getCurrentPlayer() {
      return currentPlayer;
  }
  
  public void setCurrentPlayer(int currentPlayer) {
      this.currentPlayer = currentPlayer;
  }
  
  /*
   * (non-Javadoc)
   * 
   * @see BoardGame#getBoard()
   */
  @Override
  public int[][] getBoard() {
      return board;
  }
  
  private void nextPlayer() {
      if (currentPlayer == 1)
          currentPlayer = 2;
      else
          currentPlayer = 1;
  }
  
  /*
   * (non-Javadoc)
   * 
   * @see BoardGame#isWinner()
   */
  @Override
  public boolean isWinner() {
  
      // TODO:check if there is a connection between either side of the board.
      // You can do this by using the 'virtual site' approach in the
      // percolation test.
      return false;
  }
  
  /**
   * THIS IS OPTIONAL:
   * Modify the main method if you wish to suit your implementation.
   * This is just an example of a test implementation. 
   * For example you may want to display the board after each turn.
   * @param args
   * 
   */
  public static void main(String[] args) {
  
      BoardGame hexGame = new Hex(4, 4);
  
      while (!hexGame.isWinner()) {
          System.out.println("It's player " + hexGame.getCurrentPlayer()
                  + "'s turn");
          System.out.println("Enter x and y location:");
          int x = StdIn.readInt();
          int y = StdIn.readInt();
  
          hexGame.takeTurn(x, y);
  
      }
  
      System.out.println("It's over. Player " + hexGame.getCurrentPlayer()
              + " wins!");
  
  }
  </code></pre>
  
  <p>}
  `</p>
  
  <p>I have already checked if the coordinates are valid and if the place on the board is free. But I can seem to get my head around finding the location and neighbours locations using WeightedQuickUnionUF. Any help would be great as I have tried everything I know so far. Here is the WeightedQuickUnionUF class. </p>
  
  <pre><code>public class WeightedQuickUnionUF {
  
      private int[] id;
      private int[] sz;
      private int count;
  
  
  public WeightedQuickUnionUF(int N){
      count = N;
      id = new int[N];
      sz = new int[N];
      for(int i = 0 ; i &lt; N; i++){
          id[i] = i;
          sz[i] = i;
          }
  }
  
  
  public int count(){
      return count;
  }
  
  public int find(int p){
      while(p != id[p])
          p = id[p];
      return p;
  }
  
  public boolean connected(int p, int q ){
      return find(p) == find(q);  
  }
  
  public void union(int p, int q){
      int i = find(p);
      int j = find(q);
      if(i == j) return;
  
      if(sz[i] &lt; sz[j]){id[i] = j; sz[j] += sz[i];}
      else             {id[j] = i; sz[i] += sz[j];}
      count--;
  }
  
  public static void main(String[] args) {
      int N = StdIn.readInt();
       WeightedQuickUnionUF uf = new  WeightedQuickUnionUF(N);
  
  
       while(!StdIn.isEmpty()){
           int p = StdIn.readInt();
           int q = StdIn.readInt();
           if(uf.connected(p,q)) continue;
           uf.union(p, q);
           StdOut.println(p + " " + q);
       }
  
       StdOut.println(uf.count() + "components");
  
      }
  
  }
  </code></pre>