pickupsticks.java

来自「java版的数据结构的完全代码 免费提供了 学习数据结构的请下载」· Java 代码 · 共 51 行

// Introduced in Chapter 15
import java.util.Scanner;

/** The game of Pick Up Sticks. */
public class PickUpSticks {

  /** For reading from the console. */
  public static final Scanner INPUT = new Scanner(System.in);

  /**
   * Directed acyclic graph indicating which sticks overlap which
   * others.
   */
  private Graph overlaps;

  /** The number of sticks is set here, but not any overlaps. */
  public PickUpSticks(int n) {
    overlaps = new Graph(n);
  }

  /** Ask the user which sticks overlap which others. */
  protected void determineOverlaps() {
    for (int i = 0; i < overlaps.size(); i++) {
      System.out.print("Which sticks overlap stick " + i
                       + " (separate with spaces)? ");
      Scanner line = new Scanner(INPUT.nextLine());
      while (line.hasNextInt()) {
        overlaps.addEdge(line.nextInt(), i);
      }
    }
  }

  /** Print an order in which the sticks can be picked up. */
  protected void solve() {
    System.out.println("\nThe sticks can be picked up in"
			          + " this order:");
    System.out.println(overlaps.topologicalSort());
  }

  /** Create and solve the game. */
  public static void main(String[] args) {
    System.out.println("Welcome to Pick Up Sticks.\n");
    System.out.print("How many sticks are there? ");
    PickUpSticks game = new PickUpSticks(INPUT.nextInt());
    INPUT.nextLine();           // To clear out input
    game.determineOverlaps();
    game.solve();
  }
  
}