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()) 
        if (ord[t] == -1) 
          { Q.put(new Edge(w, t)); ord[t] = cnt++; }
        else 
          if (st[t] == -1) Q.update(new Edge(w, t));
    }
}
-----
class EdgeGQ
  {
    private Edge[] s; private int N;
    EdgeGQ(int maxN)
      { s = new Edge[maxN + 1]; N = 0; }
    boolean empty()
      { return (N == 0); }
    void put(Edge item)
      { s[N++] = item; }
    void update(Edge x) { }
    Edge get()
      { int i = (int) (N*Math.random());
        Edge t = s[i]; s[i] = s[N-1]; s[N-1] = t;
        return s[--N]; 
      }
  }

----------
CHAPTER 19. Digraphs and DAGs
-----
static Graph reverse(Graph G)
  { Graph R = new Graph(G.V(), true);
    for (int v = 0; v < G.V(); v++) 
      {
        AdjList A = G.getAdjList(v);
        for (int w = A.beg(); !A.end(); w = A.nxt()) 
          R.insert(new Edge(w, v));
      }
    return R;
  }
-----
class GraphDFS
{ private Graph G;
  private int depth, cnt, cntP;
  private int[] pre, post; 
  private void show(String s, Edge e)
    { 
      for (int k = 0; k < depth; k++) 
        Out.print("  ");
      Out.println(e.v + "-" + e.w + " " + s); 
    }
  private void dfsR(Edge e)
    { int w = e.w; show("tree", e); 
      pre[w] = cnt++; depth++;
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        { Edge x = new Edge(w, t);
          if (pre[t] == -1) dfsR(x);
          else if (post[t] == -1) show("back", x);
          else if (pre[t] > pre[w]) show("down", x);
          else show("cross", x);
        }
      post[w] = cntP++; depth--;
    }
  GraphDFS(Graph G, int v)  
    { this.G = G; depth = 0; cnt = 0; cntP = 0;
      pre = new int[G.V()]; post = new int[G.V()];
      for (int t = 0; t < G.V(); t++)
        { pre[t] = -1; post[t] = -1; }
      for (int t = 0; t < G.V(); t++)
        if (pre[t] == -1) dfsR(new Edge(t, t)); 
    }
}
-----
class GraphTC
{ private DenseGraph T;
  GraphTC(Graph G)  
    { 
      T = GraphUtilities.densecopy(G);
      for (int s = 0; s < T.V(); s++) 
        T.insert(new Edge(s, s));
      for (int i = 0; i < T.V(); i++)
        for (int s = 0; s < T.V(); s++)
          if (T.edge(s, i))
            for (int t = 0; t < T.V(); t++)
              if (T.edge(i, t))
                T.insert(new Edge(s, t));
    }
  boolean reachable(int s, int t)
    { return T.edge(s, t); }
}
-----
class GraphTC
{ private Graph G;
  private DenseGraph T;
  void tcR(int v, int w)  
    { 
      T.insert(new Edge(v, w));
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (!T.edge(v, t)) tcR(v, t);
    }
  GraphTC(Graph G)  
    { this.G = G; T = new DenseGraph(G.V(), true);
      for (int v = 0; v < T.V(); v++) tcR(v, v); }
  boolean reachable(int v, int w)
    { return T.edge(v, w); }
}
-----
int compressR(Node h)
  { 
    if (h == null) return 0;
    l = compressR(h.l); 
    r = compressR(h.r);
    t = st.index(l + "", r + "");
    adj[t].l = l; adj[t].r = r;
    return t;
  }
-----
class DagTS
{ private Graph G;
  private int cnt, tcnt;
  private int[] pre, post, postI;
  private void tsR(int v)  
    { 
      pre[v] = cnt++;
      AdjList A = G.getAdjList(v);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (pre[t] == -1) tsR(t);
      post[v] = tcnt; postI[tcnt++] = v;
    }
  DagTS(Graph G)  
    { this.G = G; cnt = 0; tcnt = 0; 
      pre = new int[G.V()]; 
      post = new int[G.V()]; postI = new int[G.V()];
      for (int t = 0; t < G.V(); t++)
        { pre[t] = -1; post[t] = -1; postI[t] = -1;}
      for (int t = 0; t < G.V(); t++)
        if (pre[t] == -1) tsR(t); 
    }
  int order(int v) { return postI[v]; }
  int relabel(int v) { return post[v]; }
}
-----
  void tsR(int v)  
    { 
      pre[v] = cnt++;
      for (int w = 0; w < D.V(); w++)
        if (D.edge(w, v))
          if (pre[w] == -1) tsR(w);
      post[v] = tcnt; postI[tcnt++] = v;
    }
-----
class DagTS
{ private Graph D;
  private int[] in, ts, tsI;
  DagTS(Graph D)  
  { this.D = D; 
    intQueue Q = new intQueue(D.V());
    in = new int[D.V()]; 
    ts = new int[D.V()]; tsI = new int[D.V()];
    for (int t = 0; t < D.V(); t++)
      { in[t] = 0; ts[t] = -1; tsI[t] = -1; }
    for (int v = 0; v < D.V(); v++) 
      {
        AdjList A = D.getAdjList(v);
        for (int t = A.beg(); !A.end(); t = A.nxt()) 
          in[t]++;
      }
    for (int v = 0; v < D.V(); v++)
      if (in[v] == 0) Q.put(v);
    for (int j = 0; !Q.empty(); j++) 
      {
        int k = Q.get(); ts[j] = k; tsI[ts[j]] = j;
        AdjList A = D.getAdjList(k);
        for (int t = A.beg(); !A.end(); t = A.nxt()) 
          if (--in[t] == 0) Q.put(t);
      }
  }
  int order(int v) { return ts[v]; }
  int relabel(int v) { return tsI[v]; }
}
-----
class GraphTC
{ private Graph G; private DenseGraph D;
  private int cnt;
  private int[] pre;
  void tcR(int w)  
    { 
      pre[w] = cnt++;
      AdjList A = D.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
      { 
        D.insert(new Edge(w, t));
        if (pre[t] > pre[w]) continue;
        if (pre[t] == -1) tcR(t);
        for (int i = 0; i < D.V(); i++)
         if (D.edge(t, i)) D.insert(new Edge(w, i));
      }
    }
  GraphTC(Graph G)  
    { this.G = G; cnt = 0;
      D = GraphUtilities.densecopy(G);
      pre = new int[G.V()];
      for (int v = 0; v < D.V(); v++) pre[v] = -1;
      for (int v = 0; v < D.V(); v++) 
        if (pre[v] == -1) tcR(v); 
    }
  boolean reachable(int v, int w)
    { return D.edge(v, w); }
}
-----
class GraphSC
{ private int cnt, scnt;
  private int[] id, postI, postR;
  private void dfsR(Graph G, int w)  
    { 
      id[w] = scnt;
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (id[t] == -1) dfsR(G, t);
      postI[cnt++] = w;
    }
  GraphSC(Graph G)  
    { Graph R = GraphUtilities.reverse(G); 
      id = new int[G.V()]; postI = new int[G.V()];
      cnt = 0; scnt = 0; 
      for (int t = 0; t < R.V(); t++) id[t] = -1;
      for (int t = 0; t < R.V(); t++)
        if (id[t] == -1) dfsR(R, t); 
      postR = new int[G.V()];
      for (int t = 0; t < R.V(); t++)
        { postR[t] = postI[t]; }
      cnt = 0; scnt = 0; 
      for (int t = 0; t < R.V(); t++) id[t] = -1;
      for (int v = G.V()-1; v >= 0; v--)
        if (id[postR[v]] == -1)
          { dfsR(G, postR[v]); scnt++; }
    }
  int count() { return scnt; }
  boolean stronglyreachable(int v, int w)
    { return id[v] == id[w]; }
}
-----
class GraphSC
{ private Graph G;
  private int cnt, scnt;
  private int[] id, pre, low;
  private intStack S;
  private void scR(int w)  
    { int t, min = low[w] = pre[w] = cnt++;
      S.push(w);
      AdjList A = G.getAdjList(w);
      for (t = A.beg(); !A.end(); t = A.nxt()) 
        { if (pre[t] == -1) scR(t);
          if (low[t] < min) min = low[t]; }
      if (min < low[w]) { low[w] = min; return; }
      do 
        { id[t = S.pop()] = scnt; low[t] = G.V(); }
      while (t != w);
      scnt++;
    }
  GraphSC(Graph G)  
    { this.G = G; 
      S = new intStack(G.V());
      id = new int[G.V()]; 
      pre = new int[G.V()]; low = new int[G.V()];
      for (int t = 0; t < G.V(); t++)
        { id[t] = -1; pre[t] = -1; low[t] = -1; }
      for (int v = G.V()-1; v >= 0; v--)
        if (pre[v] == -1) scR(v); 
    }
  int count() { return scnt; }
  boolean stronglyreachable(int v, int w)
    { return id[v] == id[w]; }
}
-----
  private void scR(int w)  
    { int v; 
      pre[w] = cnt++;
      S.push(w); P.push(w);
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (pre[t] == -1) scR(t);
        else if (id[t] == -1) 
          while (pre[P.top()] > pre[t]) P.pop();
      if (P.top() == w) P.pop(); else return;
      do { id[v = S.pop()] = scnt; } while (v != w);
      scnt++;
    }
-----
class GraphTC
{ private GraphSC Gsc;
  private DagTC Ktc;
  GraphTC(Graph G)  
    { DenseGraph K;
      Gsc = new GraphSC(G);
      K = new DenseGraph(Gsc.count(), true);
      for (int v = 0; v < G.V(); v++) 
       { 
        AdjList A = G.getAdjList(v);
        for (int t = A.beg(); !A.end(); t = A.nxt()) 
          K.insert(new Edge(Gsc.ID(v), Gsc.ID(t))); 
       }
      Ktc = new DagTC(K);
    }
  boolean reachable(int v, int w)
    { return Ktc.reachable(Gsc.ID(v), Gsc.ID(w));}
}

----------
CHAPTER 20. Minimum Spanning Trees
-----
class Edge implements Item // ADT interface
  { // implementations and private members hidden
    Edge(int, int, double)
    int v()
    int w()
    double wt()
    boolean from(int)
    int other(int)
    public boolean less(Item)
    public String toString() 
  }
class Graph // ADT interface
  { // implementations and private members hidden
    Graph(int, boolean)
    int V()
    int E()
    boolean directed()
    int insert(Edge)
    void remove(Edge)
    Edge edge(int, int)
    AdjList getAdjList(int)
  }
-----
class Graph
  { private int Vcnt, Ecnt;
    private boolean digraph;
    private Edge adj[][];
    Graph(int V, boolean flag)
      {
        Vcnt = V; Ecnt = 0; digraph = flag;
        adj = new Edge[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] == null) Ecnt++;
        adj[v][w] = e;
        if (!digraph) adj[w][v] = e; 
      } 
    void remove(Edge e)
      { int v = e.v(), w = e.w();
        if (adj[v][w] == null) Ecnt--;
        adj[v][w] = null;
        if (!digraph) adj[w][v] = null; 
      } 
    Edge edge(int v, int w) 
      { return adj[v][w]; }
    AdjList getAdjList(int v)
      // Program 20.4
  }
-----
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 Edge beg()
      { i = -1; return nxt(); }
    public Edge nxt()
      {
        for (i++; i < V(); i++)
          if (edge(v, i) != null) 
            return edge(v, i);
        return null;
      }
    public boolean end()
      { return i >= V(); }
  }
-----
class Graph // sparse multigraph implementation
  { private int Vcnt, Ecnt;
    private boolean digraph;
    private class Node
      { Edge e; Node next;
        Node(Edge x, Node t) { e = 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(e, adj[v]);
        if (!digraph) adj[w] = new Node(e, adj[w]); 
        Ecnt++;
      } 
    AdjList getAdjList(int v)
      // See Program 17.10 and Exercise 20.13
  }
-----
static Edge[] edges(Graph G)
{ Edge[] a = new Edge[G.E()];
  int E = 0; 
  for (int v = 0; v < G.V(); v++) 
    {
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        if (e.from(v)) a[E++] = e;
    }
  return a;
}
-----
class GraphMST
{ 
  private double[] wt;
  private Edge[] fr, mst;
  GraphMST(Graph G)
    { 
      wt = new double[G.V()];
      mst = new Edge[G.V()]; fr = new Edge[G.V()];
      for (int v = 0; v < G.V(); v++) wt[v] = maxWT; 
      int min = -1; 
      for (int v = 0; min != 0; v = min) 
        { Edge e;
          min = 0;
          for (int w = 1; w < G.V(); w++) 
            if (mst[w] == null)
              { double P = 0.0; e = G.edge(v, w);
                if (e != null)
                  if ((P = e.wt()) < wt[w])
                    { wt[w] = P; fr[w] = e; }
                if (wt[w] < wt[min]) min = w;
              }
          if (min != 0) mst[min] = fr[min];
        }
    }
}
-----
class GraphMST
{ private double[] wt; private Edge[] fr, mst;
  private void pfs(Graph G, int s)
  { doublePQi pQ = new doublePQi(G.V(), wt);
    pQ.insert(s);
    while (!pQ.empty())
    { int v = pQ.getmin();
      mst[v] = fr[v];        
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { double P = e.wt(); int w = e.other(v); 
          if (fr[w] == null)
            { wt[w] = P; pQ.insert(w); fr[w] = e; }
          else if (mst[w] == null && P < wt[w])
            { wt[w] = P; pQ.lower(w); fr[w] = e; }
        }
    }
  }
  GraphMST(Graph G)  
    { wt = new double[G.V()];
      mst = new Edge[G.V()]; fr = new Edge[G.V()];
      for (int v = 0; v < G.V(); v++) wt[v] = -1.0; 
      for (int v = 0; v < G.V(); v++)
        if (mst[v] == null) pfs(G, v);
    }
}
-----
class GraphMST
{ private int V;
  private UF uf;
  private Edge[] a, mst;
  GraphMST(Graph G)
    { int v, w, E;
      E = G.E(); V = G.V();
      mst = new Edge[V]; 
      uf = new UF(V);
      a = GraphUtilities.edges(G);
      Sort.sort(a, 0, E-1);
      for (int i = 0, k = 1; i < E && k < V; i++)
        if (!uf.find(v = a[i].v(), w = a[i].w()))
          { uf.unite(v, w); mst[k++] = a[i]; }
    }
}
-----
class GraphMST
{ private UF uf;
  private Edge[] a, b, mst;
  GraphMST(Graph G)
  { Edge z = new Edge(0, 0, maxWT);
    uf = new UF(G.V());
    a = GraphUtilities.edges(G); 
    b = new Edge[G.V()]; mst = new Edge[G.V()+1]; 
    int N, k = 1;
    for (int E = G.E(); E != 0; E = N) 
      { int h, i, j;
        for (int t = 0; t < G.V(); t++) b[t] = z;
        for (h = 0, N = 0; h < E; h++) 
          { Edge e = a[h];
            i = uf.find(e.v()); j = uf.find(e.w());
            if (i == j) continue;
            if (e.wt() < b[i].wt()) b[i] = e;
            if (e.wt() < b[j].wt()) b[j] = e;
            a[N++] = e;
          }
        for (h = 0; h < G.V(); h++) 
         if (b[h] != z)
          if (!uf.find(i = b[h].v(), j = b[h].w()))
            { uf.unite(i, j); mst[k++] = b[h]; }
      }
  }
}
-----
class doublePQi 
{ private int N, d = 3; 
  private double[] a; private int[] pq, qp; 
  private boolean less(int i, int j)
    { return a[pq[i]] < a[pq[j]]; }
  private void exch(int i, int j)
    { int t = pq[i]; pq[i] = pq[j]; pq[j] = t;
      qp[pq[i]] = i; qp[pq[j]] = j; }
  private void swim(int k)
    { while (k > 1 && less(k, (k+d-2)/d))
        { exch(k, (k+d-2)/d); k = (k+d-2)/d; } }
  private void sink(int k, int N)
    { int j;
      while ((j = d*(k-1)+2) <= N)
        { 
          for (int i = j+1; i < j+d && i <= N; i++)
            if (less(i, j)) j = i;
          if (!(less(j, k))) break;
          exch(k, j); k = j;
        }
    }
  doublePQi(int maxN, double[] a)
    { this.a = a; this.N = 0;
      pq = new int[maxN+1]; qp = new int[maxN+1];
      for (int i = 0; i <= maxN; i++) 
        { pq[i] = 0; qp[i] = 0; }
    }
  boolean empty() { return N == 0; }
  void insert(int v) 
    { pq[++N] = v; qp[v] = N; swim(N); }
  int getmin()
    { exch(1, N); sink(1, N-1); return pq[N--]; }
  void lower(int k)
    { swim(qp[k]); }
}

----------
CHAPTER 21. Shortest Paths
-----
class GraphSPT
{ private double[] wt;
  private Edge[] spt;
  GraphSPT(Graph G, int s)  
  { int V = G.V();
    wt = new double[V]; spt = new Edge[V]; 
    for (int v = 0; v < V; v++) wt[v] = maxWT; 
    doublePQi pQ = new doublePQi(V, wt);
    for (int v = 0; v < V; v++) pQ.insert(v);
    wt[s] = 0.0; pQ.lower(s);  
    while (!pQ.empty()) 
    { int v = pQ.getmin(); // wt[v] = 0.0;
      if (v != s && spt[v] == null) return; 
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e.other(v); 
          double P = wt[v] + e.wt();
          if (P < wt[w]) 
            { wt[w] = P; pQ.lower(w); spt[w] = e; }
        }
    }
  }
  Edge pathR(int v) { return spt[v]; }
  double dist(int v) { return wt[v]; }
}
-----
class GraphSPall // ADT interface
  { // implementations and private members hidden
    GraphSPall(GRAPH G)
    Edge path(int, int)
    Edge pathR(int, int)
    double dist(int, int)
  }
-----
static double diameter(Graph G)
{ int vmax = 0, wmax = 0;
  GraphSPall all = new GraphSPall(G);
  for (int v = 0; v < G.V(); v++)
    for (int w = 0; w < G.V(); w++)
      if (all.path(v, w) != null)
        if (all.dist(v, w) > all.dist(vmax, wmax))
          { vmax = v; wmax = w; }
  int v = vmax; Out.print(v + "");
  while (v != wmax) 
  { v = all.path(v, wmax).w(); Out.print("-" + v); }
  return all.dist(vmax, wmax);
}
-----
class GraphSPall
{ private GraphSPT[] A;
  GraphSPall(Graph G)  
    { 
      A = new GraphSPT[G.V()];
      for (int v = 0; v < G.V(); v++) 
        A[v] = new GraphSPT(G, v); 
    }
  Edge pathR(int s, int t) 
    { return A[s].pathR(t); }
  double dist(int s, int t) 
    { return A[s].dist(t); }
}
-----
class GraphSPall
{ private Edge[][] p;
  private double[][] d;
  GraphSPall(Graph G)  
    { int V = G.V();
      p = new Edge[V][V]; d = new double[V][V];
      for (int s = 0; s < V; s++) 
        for (int t = 0; t < V; t++) 
          d[s][t] = maxWT; 
      for (int s = 0; s < V; s++)
        for (int t = 0; t < V; t++) 
          if (G.edge(s, t) != null)
            { p[s][t] = G.edge(s, t); 
              d[s][t] = G.edge(s, t).wt(); } 
      for (int s = 0; s < V; s++) d[s][s] = 0.0;
      for (int i = 0; i < V; i++)
        for (int s = 0; s < V; s++)
          if (p[s][i] != null)
            for (int t = 0; t < V; t++)
              if (s != t) 
                if (d[s][t] > d[s][i] + d[i][t])
                  { p[s][t] = p[s][i];
                    d[s][t] = d[s][i] + d[i][t]; }
    }
  Edge path(int s, int t) 
    { return p[s][t]; }
  double dist(int s, int t) 
    { return d[s][t]; }
}
-----
class DagLPT
{ private double[] wt;
  private Edge[] lpt;
  DagLPT(Graph G)  
  { 
    wt = new double[G.V()]; lpt = new Edge[G.V()]; 
    DagTS ts = new DagTS(G);
    for (int j = 0; j < G.V(); j++) 
     { int v = ts.order(j);
       AdjList A = G.getAdjList(v);
       for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
         { int w = e.w();
           if (wt[w] < wt[v] + e.wt())
             { wt[w] = wt[v] + e.wt(); lpt[w] = e; }       
         }
     }
  }
  Edge pathR(int v) { return lpt[v]; }
  double dist(int v) { return wt[v]; }
}
-----
class DagSPall
{ 
  private Edge[][] p;
  private double[][] d;
  void dfsR(Graph G, int s)  
    { AdjList A = G.getAdjList(s);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
      { int t = e.w(); double w = e.wt();
        if (d[s][t] > w)
          { d[s][t] = w; p[s][t] = e; }
        if (p[t][t] == null) dfsR(G, t);
        for (int i = 0; i < G.V(); i++)
          if (p[t][i] != null)
            if (d[s][i] > w + d[t][i])
            { d[s][i] = w + d[t][i]; p[s][i] = e; }
      }
    }
  DagSPall(Graph G)  
    { int V = G.V();
      p = new Edge[V][V]; d = new double[V][V];
      for (int s = 0; s < V; s++) 
        for (int t = 0; t < V; t++) 
          d[s][t] = maxWT; 
      for (int s = 0; s < V; s++)
        if (p[s][s] == null) dfsR(G, s);
    }
  Edge path(int s, int t) 
    { return p[s][t]; }
  double dist(int s, int t) 
    { return d[s][t]; }
}
-----
class Schedule
  {
    public static void main(String[] args)
      { int N = Integer.parseInt(args[0]);
        double[] duration = new double[N];
        Graph G = new Graph(N, true);
        In.init();
        for (int i = 0; i < N; i++) 
          duration[i] = In.getDouble();
        while (!In.empty())
          { int s = In.getInt(), t = In.getInt();
            G.insert(new Edge(s, t, duration[s])); }
        if (!GraphUtilities.acyclic(G)) 
          { Out.println("not feasible"); return; }
        DagLPT lpt = new DagLPT(G);
        for (int i = 0; i < N; i++)
          Out.println(i + "  " + lpt.dist(i));
      }
  }  
-----
  GraphSPT(Graph G, int s)  
  { int V = G.V(), N = 0;
    wt = new double[V]; spt = new Edge[V]; 
    for (int v = 0; v < V; v++) wt[v] = maxWT; 
    intQueue Q = new intQueue(G.E());
    wt[s] = 0.0; Q.put(s);  Q.put(V);
    while (!Q.empty()) 
    { int v;
      while ((v = Q.get()) == V) 
        { if (N++ > V) return; Q.put(V); }
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e.other(v); 
          double P = wt[v] + e.wt();
          if (P < wt[w]) 
            { wt[w] = P; Q.put(w); spt[w] = e; }
        }
    }
  }

----------
CHAPTER 22. Network Flow
-----
static int flow(Network G, int v) 
  { int x = 0;
    AdjList A = G.getAdjList(v);
    for (Edge e = A.beg(); !A.end(); e = A.nxt())
      x += e.from(v) ? e.flow() : -e.flow();
    return x; 
  }
static boolean flowcheck(Network G, int s, int t) 
  { 
    for (int v = 0; v < G.V(); v++)
      if ((v != s) && (v != t))
        if (flow(G, v) != 0) return false;
    int sflow = flow(G, s);
    if (sflow < 0) return false;
    if (sflow + flow(G, t) != 0) return false;
    return true; 
  }    
-----
class Edge
  { private int pv, pw, pcap, pflow;
    Edge(int v, int w, int cap)
      { pv = v; pw = w; pcap = cap; pflow = 0; }
    int v() { return pv; }  
    int w() { return pw; }
    int cap() { return pcap; }
    int flow() { return pflow; }
    boolean from (int v)
      { return pv == v; } 
    int other(int v)
      { return from(v) ? pw : pv; } 
    int capRto(int v)
      { return from(v) ? pflow : pcap - pflow; }
    void addflowRto(int v, int d) 
      { pflow += from(v) ? -d : d; }
  }
-----
class NetworkMaxFlow
{ private Network G; private int s, t;
  private int[] wt;
  private Edge[] st;
  private int ST(int v) { return st[v].other(v); }
  private void augment(int s, int t)
    { int d = st[t].capRto(t);
      for (int v = ST(t); v != s; v = ST(v))
        if (st[v].capRto(v) < d) 
          d = st[v].capRto(v);
      st[t].addflowRto(t, d); 
      for (int v = ST(t); v != s; v = ST(v))
        st[v].addflowRto(v, d); 
    }
  private boolean pfs()
    // Program 22.4
  NetworkMaxFlow(Network G, int s, int t)  
    { this.G = G; this.s = s; this.t = t;
      wt = new int[G.V()]; st = new Edge[G.V()];
      while (pfs()) augment(s, t);
    }
}
-----
private boolean pfs()
{ intPQi pQ = new intPQi(G.V(), wt);
  for (int v = 0; v < G.V(); v++) 
    { wt[v] = 0; st[v] = null; pQ.insert(v); }
  wt[s] = -Edge.M; pQ.lower(s);  
  while (!pQ.empty()) 
    { int v = pQ.getmin(); wt[v] = -Edge.M; 
      if (v == t) break;  
      if (v != s && st[v] == null) break;  
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e.other(v);
          int cap = e.capRto(w);
          int P = cap < -wt[v] ? cap : -wt[v];
          if (cap > 0 && -P < wt[w]) 
            { wt[w] = -P; pQ.lower(w); st[w] = e; }
        }
    }
  return st[t] != null;
}
-----
class NetworkMaxFlow
{ private Network G; private int s, t;
  private int[] h, wt;
  private void initheights()
    // See Exercise 22.52
  NetworkMaxFlow(Network G, int s, int t)  
  { this.G = G; this.s = s; this.t = t;
    wt = new int[G.V()]; h = new int[G.V()];
    initheights();
    intGQ gQ = new intGQ(G.V());
    gQ.put(s); wt[t] = -(wt[s] = Edge.M*G.V());
    while (!gQ.empty()) 
    { int v = gQ.get();
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e.other(v), cap = e.capRto(w);
          int P = cap < wt[v] ? cap : wt[v];
          if (P > 0 && v == s || h[v] == h[w]+1) 
            { e.addflowRto(w, P); 
              wt[v] -= P; wt[w] += P;
              if ((w != s) && (w != t)) gQ.put(w); 
            }
        }
      if (v != s && v != t && wt[v] > 0)
        { h[v]++; gQ.put(v); }
    }
  }
}
-----
class NetworkFeasibleFlow
{ 
  NetworkFeasibleFlow(Network G, int[] sd)  
  { 
    Network F = new Network(G.V()+2);
    for (int v = 0; v < G.V(); v++) 
     { AdjList A = G.getAdjList(v);
       for (Edge e = A.beg(); !A.end(); e = A.nxt())  
         F.insert(e);
     }    
    int s = G.V(), t = G.V()+1;
    for (int i = 0; i < G.V(); i++)
      if (sd[i] >= 0) 
           F.insert(new Edge(s, i, sd[i]));
      else F.insert(new Edge(i, t, -sd[i]));
    NetworkMaxFlow M = new NetworkMaxFlow(F, s, t);
  }
}
-----
class BipartiteMatch
{
  public static void main(String[] args)
  { int N = Integer.parseInt(args[0]);
    int s = 2*N, t = 2*N+1;
    Network G = new Network(2*N + 2);
    for (int i = 0; i < N; i++)
      G.insert(new Edge(s, i, 1));
    for (int i = N; i < 2*N; i++)
      G.insert(new Edge(i, t, 1));
    for (In.init(); !In.empty(); )
      G.insert(new Edge(In.getInt(),In.getInt(),1));
    NetworkMaxFlow M = new NetworkMaxFlow(G, s, t);
    for (int i = 0; i < N; i++) 
    {
      AdjList A = G.getAdjList(i);
      for (Edge e = A.beg(); !A.end(); e = A.nxt())
        if (e.flow() == 1 &&  e.from(i))
          Out.println(e.v() + "-" + e.w());
    }
  }
}  
-----
static int cost(Network G)
{ int x = 0;
  for (int v = 0; v < G.V(); v++) 
    { 
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt())
        if (e.from(v) && e.costRto(e.w()) < Edge.C)
          x += e.flow()*e.costRto(e.w()); 
    }
  return x; 
}
-----
class NetworkMinCost
{ private Network G; private int s, t;
  private Edge[] st;
  private int ST(int v) { return st[v].other(v); }
  private void augment(int s, int t)
    // See Program 22.3 
  private int negcyc()
    // See Exercise 22.108
  NetworkMinCost(Network G, int s, int t)  
   { this.G = G; this.s = s; this.t = t;
     st = new Edge[G.V()];
     NetworkMaxFlow M = new NetworkMaxFlow(G, s, t);
     for (int x = negcyc(); x != -1; x = negcyc())
       { augment(x, x); }
   }
}
-----
private int phiR(int v) 
  { 
    if (mark[v] == valid) return phi[v];
    phi[v] = phiR(ST(v)) - st[v].costRto(v);
    mark[v] = valid;
    return phi[v]; 
  }
-----
private int lca(int v, int w) 
  { mark[v] = ++valid; mark[w] = valid;
    while (v != w)
      { 
        if (v != t) v = ST(v);
        if (v != t && mark[v] == valid) return v;
        mark[v] = valid;
        if (w != t) w = ST(w); 
        if (w != t && mark[w] == valid) return w;
        mark[w] = valid; 
      }
    return v; 
  }
private Edge augment(Edge x)
  { int v = x.v(), w = x.w(); int r = lca(v, w);
    int d = x.capRto(w);
    for (int u = w; u != r; u = ST(u))
      if (st[u].capRto(ST(u)) < d) 
        d = st[u].capRto(ST(u));
    for (int u = v; u != r; u = ST(u))
      if (st[u].capRto(u) < d) 
        d = st[u].capRto(u);
    x.addflowRto(w, d); Edge e = x;
    for (int u = w; u != r; u = ST(u))
      { st[u].addflowRto(ST(u), d); 
        if (st[u].capRto(ST(u)) == 0) e = st[u]; }
    for (int u = v; u != r; u = ST(u))
      { st[u].addflowRto(u, d); 
        if (st[u].capRto(u) == 0) e = st[u]; }
    return e;
  }
-----
private boolean onpath(int a, int b, int c)
  { 
    for (int i = a; i != c; i = ST(i))
      if (i == b) return true;
    return false; 
  }
private void reverse(int u, int x)
  { Edge e = st[u];
    for (int i = ST(u); i != x; i = ST(i))
      { Edge y = st[i]; st[i] = e; e = y; } 
  }
private void subs(Edge w, Edge y) 
  { int u = y.w(), v = y.v(), x = w.w();
    if (st[x] != w) x = w.v(); 
    int r = lca(u, v);
    if (onpath(u, x, r))
      { reverse(u, x); st[u] = y; return; }
    if (onpath(v, x, r))
      { reverse(v, x); st[v] = y; return; } 
  }
-----
private int costR(Edge e, int v)
  { int R = e.cost() + phi[e.w()] - phi[e.v()];
    return  e.from(v) ? R : -R; }
private Edge besteligible()
  { Edge x = null; int V = G.V();
    for (int v = 0, min = Edge.C*V; v < V; v++) 
    {
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt())
        if (e.capRto(e.other(v)) > 0) 
          if (e.capRto(v) == 0)
            if (costR(e, v) < min) 
              { x = e; min = costR(e, v); } 
    }
    return x;
  }
-----
class NetworkMinCost
{ private Network G; private int s, t, valid;
  private Edge[] st;
  private int[] mark, phi;
  private int ST(int v) { return st[v].other(v); }
  private void dfsR(Edge x, int v) 
    // See Exercise 22.117   
  private int phiR(int v)           // Program 22.10   
  private Edge augment(Edge x)      // Program 22.11 
  private void subs(Edge w, Edge y) // Program 22.12
  private int costR(Edge e, int v)  // Program 22.13
  private Edge besteligible()       // Program 22.13
  NetworkMinCost(Network G, int s, int t)  
    { int V = G.V(); 
      this.G = G; this.s = s; this.t = t; 
      st = new Edge[V];
      mark = new int[V]; phi = new int[V];
      for (int i = 0; i < V; i++) mark[i] = -1;
      Edge z = new Edge(s, t, Edge.M*V, Edge.C*V);
      G.insert(z); z.addflowRto(t, z.cap()); 
      dfsR(z, t);
      for (valid = 1; ; valid++ ) 
        { 
          phi[t] = z.costRto(s); mark[t] = valid; 
          for (int v = 0; v < V; v++) 
            if (v != t) phi[v] = phiR(v);
          Edge x = besteligible();
          if (costR(x, x.v()) == 0) break;
          subs(augment(x), x);
        }
      G.remove(z);
    }
}
-----
int old = 0;
for (valid = 1; valid != old; ) 
  {
    old = valid;
    for (int v = 0; v < G.V(); v++) 
    {
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt())
        if (e.capRto(e.other(v)) > 0)
          if (e.capRto(v) == 0)
            { subs(augment(e), e); valid++; }
    }
  }