COS226

• Download UFExample1.java

/******************************************************************************
 *  Name:    Andy Guna 
 *  NetID:   guna@princeton.edu
 *  Precept: P99
 *
 *  Description: This program demonstrates the use of various classes in
 *  algs4.jar (WeightedQuickUnionUF, StdRandom, Stopwatch, and StdOut).
 *
 *  The code addresses the following problem. Given a set of n vertices,
 *  suppose that in each step you select two vertices at random and 
 *  connect them with an edge. How many steps will it take until there is
 *  a path between two specified vertices?
 *
*******************************************************************************/

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
  
public class UFExample1 {
    public static void main(String[] args) { 
        Stopwatch timer = new Stopwatch();
        int n = Integer.parseInt(args[0]);

        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(n);

        for (int steps = 1; true; steps++) {

            // pick two vertices, uniformly at random
            int v = StdRandom.uniform(n);
            int w = StdRandom.uniform(n);

            // add edge v-w
            uf.union(v, w);
            StdOut.println("adding edge " + v + "-" + w);

            // stop if vertices 0 and n-1 are connected
            if (uf.connected(0, n-1)) {
                StdOut.println("connected after " + steps + " steps");
                break;
            }
        }

        StdOut.println("elapsed time = " + timer.elapsedTime());
    }
}