This file contains the code from "Algorithms in Java, Third Edition,        Part 5," by Robert Sedgewick, and is covered under the copyright        and warranty notices in that book. Permission is granted for this        code to be used for educational purposes in association with the text,        and for other uses not covered by copyright laws, provided that        the following notice is included with the code:                "This code is from "Algorithms in Java, Third Edition,"                by Robert Sedgewick, Addison-Wesley, 2003."        Commercial uses of this code require the explicit written        permission of the publisher. Send your request for permission,        stating clearly what code you would like to use, and in what        specific way, to: aw.cse@aw.com----------CHAPTER 17. Graph Properties and Types-----class Graph // ADT interface  { // implementations and private members hidden    Graph(int, boolean)    int V()    int E()    boolean directed()    int insert(Edge)    void remove(Edge)    boolean edge(int, int)    AdjList getAdjList(int)  }-----static Edge[] edges(Graph G)  { int E = 0;    Edge[] a = new Edge[G.E()];    for (int v = 0; v < G.V(); v++)       {        AdjList A = G.getAdjList(v);        for (int w = A.beg(); !A.end(); w = A.nxt())           if (G.directed() || v < w)            a[E++] = new Edge(v, w);      }    return a;  }  -----static void show(Graph G)  {     for (int s = 0; s < G.V(); s++)       {        Out.print(s + ": ");        AdjList A = G.getAdjList(s);        for (int t = A.beg(); !A.end(); t = A.nxt())           { Out.print(t + " "); }        Out.println("");      }  }-----class GraphIO  {    static void scanEZ(Graph)    static void scan(Graph)    static void show(Graph)  }-----class GraphCC  {     GraphCC(Graph G)    int count()    boolean connect(int, int)  }-----class DriverExample  {    public static void main(String[] args)      { int V = Integer.parseInt(args[0]);        Graph G = new Graph(V, false);        GraphIO.scanEZ(G);        if (V < 20) GraphIO.show(G);        Out.print(G.E() + " edges ");        GraphCC Gcc = new GraphCC(G);        Out.println(Gcc.count() + " components");       }  }-----class Graph  {     private int Vcnt, Ecnt;    private boolean digraph;    private boolean adj[][];    Graph(int V, boolean flag)      {        Vcnt = V; Ecnt = 0; digraph = flag;        adj = new boolean[V][V];      }    int V() { return Vcnt; }    int E() { return Ecnt; }    boolean directed() { return digraph; }    void insert(Edge e)      { int v = e.v, w = e.w;        if (adj[v][w] == false) Ecnt++;        adj[v][w] = true;        if (!digraph) adj[w][v] = true;       }     void remove(Edge e)      { int v = e.v, w = e.w;        if (adj[v][w] == true) Ecnt--;        adj[v][w] = false;        if (!digraph) adj[w][v] = false;       }     boolean edge(int v, int w)      { return adj[v][w]; }    AdjList getAdjList(int v)      // Program 17.8  }-----AdjList getAdjList(int v)  { return new AdjArray(v); }private class AdjArray implements AdjList  {     private int i, v;    AdjArray(int v)      { this.v = v; i = -1; }    public int beg()      { i = -1; return nxt(); }    public int nxt()      {        for (i++; i < V(); i++)          if (edge(v, i) == true) return i;        return -1;      }    public boolean end()      { return i >= V(); }  }-----class Graph // sparse multigraph implementation  {     private int Vcnt, Ecnt;    private boolean digraph;    private class Node      { int v; Node next;	Node(int x, Node t) { v = x; next = t; }      }    private Node adj[];    Graph(int V, boolean flag)      {        Vcnt = V; Ecnt = 0; digraph = flag;        adj = new Node[V];      }    int V() { return Vcnt; }    int E() { return Ecnt; }    boolean directed() { return digraph; }    void insert(Edge e)      { int v = e.v, w = e.w;        adj[v] = new Node(w, adj[v]);        if (!digraph) adj[w] = new Node(v, adj[w]);         Ecnt++;      }     AdjList getAdjList(int v)      // Program 17.10  }-----AdjList getAdjList(int v)  { return new AdjLinkedList(v); }private class AdjLinkedList implements AdjList  {     private int v;    private Node t;    AdjLinkedList(int v)      { this.v = v; t = null; }    public int beg()      { t = adj[v];         return t == null ? -1 : t.v; }    public int nxt()      { if (t != null) t = t.next;         return t == null ? -1 : t.v; }    public boolean end()      { return t == null; }  }-----class GraphDegree{  private Graph G;  private int[] deg;   GraphDegree(Graph G)    { this.G = G;       deg = new int[G.V()];      for (int v = 0; v < G.V(); v++)       {         deg[v] = 0;        AdjList A = G.getAdjList(v);        for (int w = A.beg(); !A.end(); w = A.nxt())           deg[v]++;       }    }  int degree(int v)    { return deg[v]; }}-----static void randE(Graph G, int E)  {     for (int i = 0; i < E; i++)      {        int v = (int) (G.V()*Math.random());        int w = (int) (G.V()*Math.random());        G.insert(new Edge(v, w));      }  }-----static void randG(Graph G, int E)  { double p = 2.0*E/G.V()/(G.V()-1);    for (int i = 0; i < G.V(); i++)      for (int j = 0; j < i; j++)        if (Math.random() < p)          G.insert(new Edge(i, j));  }-----static void scan(Graph G)  { int v, w;    ST st = new ST();    for (In.init(); !In.empty(); )      {         v = st.index(In.getString());        w = st.index(In.getString());        G.insert(new Edge(v, w));       }  }-----class ST
  {
    private final static int END = 0;
    private int N, val;
    private class Node
      { char c; int v; Node l, m, r; }
    private Node head;
    private Node indexR(Node h, char[] s, int i)
      { char ch = (i < s.length) ? s[i] : END;
        if (h == null) 
          { h = new Node(); h.c = ch; h.v = -1; }
        if (ch == END) 
          {
            if (h.v == -1) h.v = N++;
            val = h.v;
            return h;
          }
        if (s[i] < h.c) h.l = indexR(h.l, s, i);
        if (s[i] == h.c) h.m = indexR(h.m, s, i+1);
        if (s[i] > h.c) h.r = indexR(h.r, s, i);
        return h;
      }
    ST()
      { head = null; N = 0; }
    int index(String key)
      { char[] s = key.toCharArray();
        head = indexR(head, s, 0); return val; }
  }
-----class GraphPath{   private Graph G;  private boolean found;  private boolean[] visited;   private boolean searchR(int v, int w)    {       if (v == w) return true;      visited[v] = true;      AdjList A = G.getAdjList(v);      for (int t = A.beg(); !A.end(); t = A.nxt())         if (!visited[t])          if (searchR(t, w)) return true;      return false;    }  GraphPath(Graph G, int v, int w)      { this.G = G; found = false;      visited = new boolean[G.V()];      found = searchR(v, w);     }  boolean exists()    { return found; }}-----  private boolean searchR(int v, int w, int d)    {       if (v == w) return (d == 0);      visited[v] = true;      AdjList A = G.getAdjList(v);      for (int t = A.beg(); !A.end(); t = A.nxt())         if (!visited[t])          if (searchR(t, w, d-1)) return true;      visited[v] = false;      return false;    }-----class GraphPathE{   private Graph G;  private int v, w;  private boolean nopath;  void show()    // See Program 17.19  GraphPathE(Graph G, int v, int w)     { this.G = G;       GraphDegree Gdeg = new GraphDegree(G);      int t = Gdeg.degree(v) + Gdeg.degree(w);      if ((t % 2) != 0) { nopath = true; return; }      for (t = 0; t < G.V(); t++)        if ((t != v) && (t != w))          if ((Gdeg.degree(t) % 2) != 0)             { nopath = true; return; }      nopath = false;    }  boolean exists()    { return !nopath; }}-----private intStack S;private int tour(int v)  {     while (true)       { AdjList A = G.AdjList(v);        int w = A.beg(); if (A.end()) break;        S.push(v);        G.remove(new Edge(v, w));        v = w;      }    return v;  }void show()  {     S = new intStack(G.E());    if (nopath) return;    while (tour(v) == v && !S.empty())      { v = S.pop(); Out.print("-" + v); }    Out.println("");  }----------CHAPTER 18. Graph Search-----class GraphDFSc{ private Graph G;  private int cnt;  private int[] ord;   private void searchC(int v)    {       ord[v] = cnt++;      AdjList A = G.getAdjList(v);      for (int t = A.beg(); !A.end(); t = A.nxt())         if (ord[t] == -1) searchC(t);    }  GraphDFSc(Graph G, int v)      { this.G = G; cnt = 0;      ord = new int[G.V()];      for (int t = 0; t < G.V(); t++)        ord[t] = -1;      searchC(v);    }  int count() { return cnt; }  int order(int v) { return ord[v]; }}-----class GraphDFS{ private Graph G;  private int cnt;  private int[] ord, st;   private void searchC(Edge e)    { int w = e.w;       ord[w] = cnt++; st[e.w] = e.v;      AdjList A = G.getAdjList(w);      for (int t = A.beg(); !A.end(); t = A.nxt())         if (ord[t] == -1) searchC(new Edge(w, t));    }  GraphDFS(Graph G, int v)      { this.G = G; cnt = 0;      ord = new int[G.V()]; st = new int[G.V()];      for (int t = 0; t < G.V(); t++)        { ord[t] = -1; st[t] = -1; }      for (int t = 0; t < G.V(); t++)        if (ord[t] == -1) searchC(new Edge(t, t));     }  int order(int v) { return ord[v]; }  int ST(int v) { return st[v]; }}-----class GraphCC  { private Graph G;    private int ccnt;    private int[] id;     private void ccR(int w)      {         id[w] = ccnt;        AdjList A = G.getAdjList(w);        for (int v = A.beg(); !A.end(); v = A.nxt())           if (id[v] == -1) ccR(v);      }    GraphCC(Graph G)      { this.G = G; ccnt = 0;        id = new int[G.V()];        for (int v = 0; v < G.V(); v++) id[v] = -1;        for (int v = 0; v < G.V(); v++)          if (id[v] == -1) { ccR(v); ccnt++; }      }    int count() { return ccnt; }    boolean connect(int s, int t)       { return id[s] == id[t]; }  }-----  private void searchC(Edge e)    { int v = e.v, w = e.w;      ord[w] = cnt++;      Out.print("-" + w);      AdjList A = G.getAdjList(w);      for (int t = A.beg(); !A.end(); t = A.nxt())         if (ord[t] == -1) searchC(new Edge(w, t));        else if (ord[t] < ord[v])          Out.print("-" + t + "-" + w);      if (v == w) Out.println("");             else Out.print("-" + v);     }-----class GraphBiCC{ private Graph G;  private boolean OK;  private int[] vc;   private boolean dfsR(int v, int c)    {       vc[v] = (c+1) % 2;      AdjList A = G.getAdjList(v);      for (int t = A.beg(); !A.end(); t = A.nxt())         if (vc[t] == -1)           { if (!dfsR(t, vc[v])) return false; }         else if (vc[t] != c) return false;      return true;    }  GraphBiCC(Graph G)      { this.G = G; OK = true;      vc = new int[G.V()];      for (int t = 0; t < G.V(); t++) vc[t] = -1;      for (int v = 0; v < G.V(); v++)        if (vc[v] == -1)           if (!dfsR(v, 0)) { OK = false; return; }    }  boolean bipartite() { return OK; }  int color(int v) { return vc[v]; }}-----class GraphECC  { private Graph G;    private int cnt, bcnt;    private int[] low, ord;     private void searchC(Edge e)      { int w = e.w;        ord[w] = cnt++; low[w] = ord[w];        AdjList A = G.getAdjList(w);        for (int t = A.beg(); !A.end(); t = A.nxt())           if (ord[t] == -1)             {              searchC(new Edge(w, t));              if (low[w] > low[t]) low[w] = low[t];              if (low[t] == ord[t])                 bcnt++; // w-t is a bridge            }      else if (t != e.v)        if (low[w] > ord[t]) low[w] = ord[t];      }    GraphECC(Graph G)      { this.G = G; bcnt = 0; cnt = 0;        ord = new int[G.V()]; low = new int[G.V()];         for (int v = 0; v < G.V(); v++)          { ord[v] = -1; low[v] = -1; }        for (int v = 0; v < G.V(); v++)          if (ord[v] == -1) searchC(new Edge(v, v));       }    int count() { return bcnt+1; }  }-----class GraphBFSedge{   private Graph G;  private int cnt;  private int[] ord, st;   private void searchC(Edge e)  { EdgeQueue Q = new EdgeQueue(G.V());    Q.put(e);    while (!Q.empty())      if (ord[(e = Q.get()).w] == -1)       { int v = e.v, w = e.w;        ord[w] = cnt++; st[w] = v;                AdjList A = G.getAdjList(w);        for (int t = A.beg(); !A.end(); t = A.nxt())           if (ord[t] == -1) Q.put(new Edge(w, t));      }  }  GraphBFSedge(Graph G, int v)      { this.G = G; cnt = 0;      ord = new int[G.V()]; st = new int[G.V()];      for (int t = 0; t < G.V(); t++)        { ord[t] = -1; st[t] = -1; }      for (int t = 0; t < G.V(); t++)        if (ord[t] == -1) searchC(new Edge(t, t));     }  int order(int v) { return ord[v]; }  int ST(int v) { return st[v]; }}-----private void searchC(Edge e)  { EdgeQueue Q = new EdgeQueue(G.V());    Q.put(e); ord[e.w] = cnt++;     while (!Q.empty())      { e = Q.get(); int v = e.v, w = e.w;        st[w] = v;                AdjList A = G.getAdjList(w);        for (int t = A.beg(); !A.end(); t = A.nxt())           if (ord[t] == -1)           { Q.put(new Edge(w, t)); ord[t] = cnt++; }      }  }-----private void searchC(Edge e){ EdgeGQ Q = new EdgeGQ(G.V());  Q.put(e); ord[e.w] = cnt++;   while (!Q.empty())    { e = Q.get(); int v = e.v, w = e.w;      st[w] = v;              AdjList A = G.getAdjList(w);      for (int t = A.beg(); !A.end(); t = A.nxt())