This file contains the code from "Algorithms in C++, 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 C++, Third Edition,"                by Robert Sedgewick, Addison-Wesley, 2002."        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-----struct Edge   { int v, w;    Edge(int v = -1, int w = -1) : v(v), w(w) { }  };class GRAPH  { private:      // Implementation-dependent code    public:      GRAPH(int, bool);      ~GRAPH();      int V() const;      int E() const;      bool directed() const;      int insert(Edge);      int remove(Edge);      bool edge(int, int);      class adjIterator        {           public:            adjIterator(const GRAPH &, int);            int beg();            int nxt();            bool end();        };  };-----template <class Graph> vector <Edge> edges(Graph &G)  { int E = 0;    vector <Edge> a(G.E());     for (int v = 0; v < G.V(); v++)       {        typename Graph::adjIterator A(G, v);        for (int w = A.beg(); !A.end(); w = A.nxt())           if (G.directed() || v < w)            a[E++] = Edge(v, w);      }    return a;  }-----template <class Graph> void IO<Graph>::show(const Graph &G)  {     for (int s = 0; s < G.V(); s++)       {        cout.width(2); cout << s << ":";        typename Graph::adjIterator A(G, s);        for (int t = A.beg(); !A.end(); t = A.nxt())           { cout.width(2); cout << t << " "; }        cout << endl;      }  }-----template <class Graph> class IO  {    public:      static void show(const Graph &);      static void scanEZ(Graph &);      static void scan(Graph &);  };-----template <class Graph> class CC  {     private:      // implementation-dependent code    public:      CC(const Graph &);      int count();      bool connect(int, int);  };-----#include <iostream.h>#include <stdlib.h>#include "GRAPH.cc"#include "IO.cc"#include "CC.cc"main(int argc, char *argv[]){ int V = atoi(argv[1]);  GRAPH G(V);  IO<GRAPH>::scan(G);  if (V < 20) IO<GRAPH>::show(G);  cout << G.E() << " edges ";  CC<GRAPH> Gcc(G);  cout << Gcc.count() << " components" << endl;}-----class DenseGRAPH{ int Vcnt, Ecnt; bool digraph;  vector <vector <bool> > adj;public:  DenseGRAPH(int V, bool digraph = false) :    adj(V), Vcnt(V), Ecnt(0), digraph(digraph)    {       for (int i = 0; i < V; i++)         adj[i].assign(V, false);    }  int V() const { return Vcnt; }  int E() const { return Ecnt; }  bool directed() const { 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;     }   bool edge(int v, int w) const     { return adj[v][w]; }  class adjIterator;  friend class adjIterator;};-----class DenseGRAPH::adjIterator{ const DenseGRAPH &G;  int i, v;public:  adjIterator(const DenseGRAPH &G, int v) :     G(G), v(v), i(-1) { }  int beg()    { i = -1; return nxt(); }  int nxt()    {      for (i++; i < G.V(); i++)        if (G.adj[v][i] == true) return i;      return -1;    }  bool end()    { return i >= G.V(); }};-----class SparseMultiGRAPH{ int Vcnt, Ecnt; bool digraph;  struct node    { int v; node* next;      node(int x, node* t) { v = x; next = t; }    };  typedef node* link;  vector <link> adj;public:  SparseMultiGRAPH(int V, bool digraph = false) :    adj(V), Vcnt(V), Ecnt(0), digraph(digraph)     { adj.assign(V, 0); }  int V() const { return Vcnt; }  int E() const { return Ecnt; }  bool directed() const { 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++;    }   void remove(Edge e);  bool edge(int v, int w) const;   class adjIterator;  friend class adjIterator;};-----class SparseMultiGRAPH::adjIterator{ const SparseMultiGRAPH &G;  int v;  link t;public:  adjIterator(const SparseMultiGRAPH &G, int v) :     G(G), v(v) { t = 0; }  int beg()    { t = G.adj[v]; return t ? t->v : -1; }  int nxt()    { if (t) t = t->next; return t ? t->v : -1; }  bool end()    { return t == 0; }};-----template <class Graph> class DEGREE{ const Graph &G;  vector <int> degree; public:  DEGREE(const Graph &G) : G(G), degree(G.V(), 0)     {       for (int v = 0; v < G.V(); v++)      { typename Graph::adjIterator A(G, v);        for (int w = A.beg(); !A.end(); w = A.nxt())           degree[v]++;      }    }  int operator[](int v) const     { return degree[v]; }};-----static void randE(Graph &G, int E)  {     for (int i = 0; i < E; i++)      {        int v = int(G.V()*rand()/(1.0+RAND_MAX));        int w = int(G.V()*rand()/(1.0+RAND_MAX));        G.insert(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 (rand() < p*RAND_MAX)          G.insert(Edge(i, j));  }-----#include "ST.cc"template <class Graph> void IO<Graph>::scan(Graph &G)  { string v, w;    ST st;    while (cin >> v >> w)      G.insert(Edge(st.index(v), st.index(w)));  }-----#include <string>class ST { int N, val;  struct node     { int v, d; node* l, *m, *r;      node(int d) : v(-1), d(d), l(0), m(0), r(0) {}    };  typedef node* link;  link head;  link indexR(link h, const string &s, int w)    { int i = s[w];      if (h == 0) h = new node(i);      if (i == 0)         {          if (h->v == -1) h->v = N++;          val = h->v;          return h;        }      if (i < h->d) h->l = indexR(h->l, s, w);      if (i == h->d) h->m = indexR(h->m, s, w+1);      if (i > h->d) h->r = indexR(h->r, s, w);      return h;    }public:  ST() : head(0), N(0) { }  int index(const string &key)    { head = indexR(head, key, 0); return val; }};-----template <class Graph> class sPATH{ const Graph &G;  vector <bool> visited;  bool found;   bool searchR(int v, int w)    {       if (v == w) return true;      visited[v] = true;      typename Graph::adjIterator A(G, v);      for (int t = A.beg(); !A.end(); t = A.nxt())         if (!visited[t])          if (searchR(t, w)) return true;      return false;    }public:  sPATH(const Graph &G, int v, int w) :     G(G), visited(G.V(), false)     { found = searchR(v, w); }  bool exists() const     { return found; }};-----  bool searchR(int v, int w, int d)    {       if (v == w) return (d == 0);      visited[v] = true;      typename Graph::adjIterator A(G, 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;    }-----template <class Graph> class ePATH{ Graph G;  int v, w;  bool found;  STACK <int> S;  int tour(int v);public:  ePATH(const Graph &G, int v, int w) :     G(G), v(v), w(w)    { DEGREE<Graph> deg(G);      int t = deg[v] + deg[w];      if ((t % 2) != 0) { found = false; return; }      for (t = 0; t < G.V(); t++)        if ((t != v) && (t != w))          if ((deg[t] % 2) != 0)             { found = false; return; }      found = true;    }  bool exists() const     { return found; }  void show();};-----template <class Graph>int ePATH<Graph>::tour(int v)  {     while (true)       { typename Graph::adjIterator A(G, v);        int w = A.beg(); if (A.end()) break;        S.push(v);        G.remove(Edge(v, w));        v = w;      }    return v;  }template <class Graph>void ePATH<Graph>::show()    {       if (!found) return;      while (tour(v) == v && !S.empty())        { v = S.pop(); cout << "-" << v; }      cout << endl;        }----------CHAPTER 18. Graph Search-----#include <vector>template <class Graph> class cDFS{ int cnt;  const Graph &G;  vector <int> ord;   void searchC(int v)    {       ord[v] = cnt++;      typename Graph::adjIterator A(G, v);      for (int t = A.beg(); !A.end(); t = A.nxt())         if (ord[t] == -1) searchC(t);    }public:  cDFS(const Graph &G, int v = 0) :     G(G), cnt(0), ord(G.V(), -1)     { searchC(v); }  int count() const { return cnt; }  int operator[](int v) const { return ord[v]; }};-----template <class Graph> class SEARCH{  protected:    const Graph &G;    int cnt;    vector <int> ord;    virtual void searchC(Edge) = 0;    void search()      { for (int v = 0; v < G.V(); v++)          if (ord[v] == -1) searchC(Edge(v, v)); }  public:    SEARCH (const Graph &G) : G(G),       ord(G.V(), -1), cnt(0) { }    int operator[](int v) const { return ord[v]; }};-----template <class Graph> class DFS : public SEARCH<Graph> { vector<int> st;  void searchC(Edge e)    { int w = e.w;       ord[w] = cnt++; st[e.w] = e.v;      typename Graph::adjIterator A(G, w);      for (int t = A.beg(); !A.end(); t = A.nxt())         if (ord[t] == -1) searchC(Edge(w, t));    }public:  DFS(const Graph &G) : SEARCH<Graph>(G),     st(G.V(), -1) { search(); }   int ST(int v) const { return st[v]; }};-----template <class Graph> class CC{ const Graph &G;  int ccnt;  vector <int> id;   void ccR(int w)    {       id[w] = ccnt;      typename Graph::adjIterator A(G, w);      for (int v = A.beg(); !A.end(); v = A.nxt())         if (id[v] == -1) ccR(v);    }public:  CC(const Graph &G) : G(G), ccnt(0), id(G.V(), -1)     {       for (int v = 0; v < G.V(); v++)        if (id[v] == -1) { ccR(v); ccnt++; }     }  int count() const { return ccnt; }  bool connect(int s, int t) const     { return id[s] == id[t]; }};-----template <class Graph> class EULER : public SEARCH<Graph> {   void searchC(Edge e)  { int v = e.v, w = e.w;    ord[w] = cnt++;    cout << "-" << w;     typename Graph::adjIterator A(G, w);    for (int t = A.beg(); !A.end(); t = A.nxt())       if (ord[t] == -1) searchC(Edge(w, t));      else if (ord[t] < ord[v])        cout << "-" << t << "-" << w;    if (v != w) cout << "-" << v; else cout << endl;    }public:  EULER(const Graph &G) : SEARCH<Graph>(G)     { search(); }};-----template <class Graph> class BI{ const Graph &G;  bool OK;  vector <int> vc;   bool dfsR(int v, int c)    {       vc[v] = (c+1) %2;      typename Graph::adjIterator A(G, 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;    }public:  BI(const Graph &G) : G(G), OK(true), vc(G.V(),-1)     {       for (int v = 0; v < G.V(); v++)        if (vc[v] == -1)           if (!dfsR(v, 0)) { OK = false; return; }    }  bool bipartite() const { return OK; }  int color(int v) const { return vc[v]; }};-----template <class Graph> class EC : public SEARCH<Graph> { int bcnt;  vector <int> low;   void searchC(Edge e)  { int w = e.w;    ord[w] = cnt++; low[w] = ord[w];    typename Graph::adjIterator A(G, w);    for (int t = A.beg(); !A.end(); t = A.nxt())       if (ord[t] == -1)         {          searchC(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];  }public:  EC(const Graph &G) : SEARCH<Graph>(G),     bcnt(0), low(G.V(), -1)    { search(); }  int count() const { return bcnt+1; }};-----#include "QUEUE.cc"template <class Graph> class BFS : public SEARCH<Graph> { vector<int> st;  void searchC(Edge e)  { QUEUE<Edge> Q;      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;                typename Graph::adjIterator A(G, w);        for (int t = A.beg(); !A.end(); t = A.nxt())           if (ord[t] == -1) Q.put(Edge(w, t));      }  }public:  BFS(Graph &G) : SEARCH<Graph>(G), st(G.V(), -1)     { search(); }  int ST(int v) const { return st[v]; }};-----  void searchC(Edge e)  { QUEUE<Edge> Q;    Q.put(e); ord[e.w] = cnt++;     while (!Q.empty())      {        e = Q.get(); st[e.w] = e.v;                typename Graph::adjIterator A(G, e.w);        for (int t = A.beg(); !A.end(); t = A.nxt())           if (ord[t] == -1)             { Q.put(Edge(e.w, t)); ord[t] = cnt++; }      }  }-----#include "GQ.cc"template <class Graph>