title: How to implement a maze using disjoint sets?
body: <p>Here's the DisjointSet class i use :</p>
  
  <pre><code>public class DisjointSet{
      public DisjointSet(int size){
          s = new int[size];
          for(int i = 0; i &lt; size; ++i){
              s[i] = -1;
          }
      }
  
      public void union(int el1, int el2){
          int root1 = find(el1);
          int root2 = find(el2);
          if(root1 == root2){
              return;
          }
  
          if(s[root2] &lt; s[root1]){
              s[root1] = root2;
          }
          else{
              if(s[root1] == s[root2]){
                  --s[root1];
              }
              s[root2] = root1;
          }
      }
  
      public int find(int x){
          if(s[x] &lt; 0){
              return x;
          }
          else{
              s[x] = find(s[x]);
              return s[x];
          }
      }
  
      private int[] s;
  }
  </code></pre>
  
  <p>And here's my Maze class : </p>
  
  <pre><code>public class Maze
  {
      public Vector&lt;Wall&gt; maze;
      public Vector&lt;Room&gt; graph;
      public Vector&lt;Integer&gt; path;
  
      public int LASTROOM;
      public int height;
      public int width;
      public Random generator;
      public DisjointSet ds;
  
      public int dsSize;
  
      public Maze(int w, int h, int seed)
      {
          width = w;
          height = h;
          dsSize = width * height;
  
          LASTROOM = dsSize-1;
  
          // Maze initialization with all walls
          maze = new Vector&lt;Wall&gt;();
          for(int i = 0; i &lt; height; ++i)
          {
              for(int j = 0; j &lt; width; ++j)
              {
                  if(i &gt; 0)
                      maze.add(new Wall(j+i*height, j+(i-1)*height));
  
                  if(j &gt; 0)
                      maze.add(new Wall(j+i*height, j-1+i*height));
              }
          }
  
          // Creation of the graph topology of the maze
          graph = new Vector&lt;Room&gt;();
          for(int i = 0; i &lt; dsSize; ++i)
              graph.add(new Room(i));
  
          // Sort the walls of random way
          generator = new Random(seed);
  
          for(int i = 0; i &lt; maze.size(); ++i)
          {
              //TODO
          }
  
          // Initialization of related structures
          ds = new DisjointSet(dsSize);
          path = new Vector&lt;Integer&gt;();
      }
  
      public void generate()
      {
          //TODO
      }
  
      public void solve()
      {
          //TODO
      }
  }
  </code></pre>
  
  <p>I've been looking for a way to implement <em>generate()</em> and <em>solve()</em> along with the random sorting of the maze's walls for a long time now, and I can't seem to find any algorithm or implementation on the Internet to do this.</p>
  
  <p><em>generate()</em> should go through the permuted walls in the maze variable and destroy it if the two parts (rooms) connected by the wall are not already in the same set. The method should also add an edge in the room graph (each room has a list of adjacency named <em>paths</em> and the <em>Room</em> class has a variable <em>id</em> that identifies each graph's vertices).</p>
  
  <p><em>solve()</em> should solve the maze path and generate the vector of the <em>Maze</em> class containing the order of the rooms to go through to get to the exit. The first room is positionned at 0 and the last room is positionned at <em>LASTROOM</em>.</p>
  
  <p>Note: <em>Maze</em> and <em>Room</em> constructors are as follow:</p>
  
  <pre><code>public Wall(int r1, int r2)
  {
      room1 = r1;
      room2 = r2;
  }
  
  public Room(int i)
  {
      id = i;
      distance = -1;
      paths = new Vector&lt;Integer&gt;();
  }
  </code></pre>
  
  <p>If someone would be kind enough to suggest an implementation that would work in Java, I would greatly appreciate it, thank you. </p>