/******************************************************************************
* 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());
}
}