Sedgwik.cpp

 
C++ Programs from Algorithms 2nd edition
 
Copyright 1992. Addison-Wesley Publishing Company, Inc.
All Rights Reserved. 
 
 
--------------------------------
CHAPTER 1 Introduction   
 
 
--------------------------------
CHAPTER 2 C++ (and C)
 
#include 
int gcd(int u, int v)
  {
    int t;
    while (u > 0)
      {
        if (u < v) { t = u; u = v; v = t; }
        u = u - v;
      }
    return v;
   }
main()
  {
    int x, y;
    while (cin >> x && cin >> y)
      if (x>0 && y>0) cout << x << ' ' << y << ' ' 
                                << gcd(x,y) << '\n';
  }
 
--------------------------------
CHAPTER 3 Elementary Data Structures 
 
const int N = 1000;
main()
  {
    int i, j, a[N+1];
    for (a[1] = 0, i = 2; i <= N; i++) a[i] = 1;
    for (i = 2; i <= N/2; i++)
      for (j = 2; j <= N/i; j++) 
        a[i*j] = 0;
    for (i = 1; i <= N; i++)
      if (a[i]) cout << i << ' ';
    cout << '\n';
  }
 
    struct node 
      { int key; struct node *next; };
 
    struct node *head, *z;
    head = new node; z = new node;
    head->next = z; z->next = z;
 
struct node 
  { int key; struct node *next; };
main()
  { 
    int i, N, M; 
    struct node *t, *x;
    cin >> N >> M;
    t = new node; t->key = 1; x = t;
    for (i = 2; i <= N; i++)
      { 
        t->next = new node;
        t = t->next; t->key = i;
      }
    t->next = x;
    while (t != t->next)
      {
        for (i = 1; i < M; i++) t = t->next;
        cout << t->next->key << ' ';
        x = t->next; t->next = x->next;
        delete x;
      }
    cout << t->key << '\n';
  }
 
    key[x] = v; next[x] = next[t]; next[t] = x++;
 
class Stack 
  {
    private:
      itemType *stack;
      int p;
    public:
      Stack(int max=100) 
        { stack = new itemType[max]; p = 0; }
     ~Stack()
        { delete stack; }
      inline void push(itemType v)
        { stack[p++] = v; }
      inline itemType pop()
        { return stack[--p]; }
      inline int empty()
        { return !p; }
  };
 
    char c; Stack acc(50); int x;
    while (cin.get(c))
      {
        x = 0;
        while (c == ' ') cin.get(c);
        if (c == '+') x = acc.pop() + acc.pop();
        if (c == '*') x = acc.pop() * acc.pop();
        while (c>='0' && c<='9')
          { x = 10*x + (c-'0');  cin.get(c); }
        acc.push(x);
      }
   cout << acc.pop() << '\n';
 
    char c; Stack save(50);
    while (cin.get(c))
      {
        if (c == ')') cout.put(save.pop());
        if (c == '+') save.push(c);
        if (c == '*') save.push(c);
        while (c>='0' && c<='9') 
          { cout.put(c); cin.get(c); } 
        if (c != '(') cout << ' ';
      }
    cout << '\n';
 
class Stack 
  {
    public:
      Stack(int max); 
     ~Stack();
      void push(itemType v);
      itemType pop();
      int empty();
    private:
      struct node 
       { itemType key; struct node *next; };
      struct node *head, *z;
  };
 
Stack::Stack(int max) 
  {
    head = new node; z = new node;
    head->next = z;  z->next = z;
  }
Stack::~Stack() 
  { 
    struct node *t = head;
    while (t != z) 
      { head = t; t = t->next; delete head; }
  }
 
void Stack::push(itemType v) 
  {
    struct node *t = new node;
    t->key = v; t->next = head->next; 
    head->next = t;
  }
itemType Stack::pop()   
  {
    itemType x;
    struct node *t = head->next; 
    head->next = t->next; x = t->key;
    delete t; return x;
  }
int Stack::empty()
  { return head->next == z; }
 
void Queue::put(itemType v)
  {
    queue[tail++] = v;
    if (tail > size) tail = 0; 
  }
itemType Queue::get()
  { 
    itemType t = queue[head++];
    if (head > size) head = 0;
    return t;
  }
int Queue::empty()
  { return head == tail; }
 
 
--------------------------------
CHAPTER 4 Trees   
 
    struct node
      { char info; struct node *l, *r; };
    struct node *x, *z;
 
    char c; Stack stack(50);
    z = new node; z->l = z; z->r = z;
    while (cin.get(c))
      {
        while (c == ' ') cin.get(c);
        x = new node;
        x->info = c; x->l = z; x->r = z;
        if (c=='+' || c=='*') 
          { x->r = stack.pop(); x->l = stack.pop(); }
        stack.push(x);
      }
 
traverse(struct node *t)
  {
    stack.push(t);
    while (!stack.empty())
      {
        t = stack.pop(); visit(t);
        if (t->r != z) stack.push(t->r); 
        if (t->l != z) stack.push(t->l); 
      }
  }
 
traverse(struct node *t)
  {
    queue.put(t);
    while (!queue.empty())
      {
        t = queue.get(); visit(t);
        if (t->l != z) queue.put(t->l); 
        if (t->r != z) queue.put(t->r); 
      }
  }
 
 
--------------------------------
CHAPTER 5 Recursion   
 
int factorial(int N)
  {
    if (N == 0) return 1;
    return N * factorial(N-1);
  }
 
int fibonacci(int N)
  {
    if (N <= 1) return 1;
    return fibonacci(N-1) + fibonacci(N-2);
  }
 
const int max = 25;
int fibonacci(int N)
  {
    int i, F[max];
    F[0] = 1; F[1] = 1;
    for (i = 2; i <= max; i++) 
        F[i] = F[i-1] + F[i-2];
    return F[N];    
  }
 
rule(int l, int r, int h)
  {
    int m = (l+r)/2;
    if (h > 0)
      { 
        mark(m,h);
        rule(l,m,h-1);
        rule(m,r,h-1);
      }
  }
 
rule(0,8,3)
   mark(4,3 )
   rule(0,4,2)
      mark(2,2)
      rule(0,2,1)
         mark(1,1)
         rule(0,1,0)
         rule(1,2,0)
      rule(2,4,1)
         mark(3,1)
         rule(2,3,0)
         rule(3,4,0)
   rule(4,8,2)
      mark(6,2)
      rule(4,6,1)
         mark(5,1)
         rule(4,5,0)
         rule(5,6,0)
      rule(6,8,1)
         mark(7,1)
         rule(6,7,0)
 
rule(0,8,3)
   rule(0,4,2)
      rule(0,2,1)
         rule(0,1,0)
         mark(1,1)
         rule(1,2,0)
      mark(2,2)
      rule(2,4,1)
         rule(2,3,0)
         mark(3,1)
         rule(3,4,0)
   mark(4,3 )
   rule(4,8,2)
      rule(4,6,1)
         rule(4,5,0)
         mark(5,1)
         rule(5,6,0)
      mark(6,2)
      rule(6,8,1)
         rule(6,7,0)
         mark(7,1)
 
rule(int l, int r, int h)
  { 
    int i, j, t;
    for (i = 1,j = 1; i <= h; i++,j+=j)
      for (t = 0; t <= (l+r)/j; t++)
        mark(l+j+t*(j+j),i);
  }
 
star(int x, int y, int r)
  {
    if (r > 0)
      {
        star(x-r,y+r,r/2);
        star(x+r,y+r,r/2);
        star(x-r,y-r,r/2);
        star(x+r,y-r,r/2);
        box(x,y,r);
      }
  }
 
traverse(struct node *t)
  {
    if (t != z)
      {
        traverse(t->l);
        visit(t);
        traverse(t->r);
      }
  }
 
visit(struct node *t)
  { t->x = ++x; t->y = y; }
traverse(struct node *t)
  {
    y++;
    if (t != z)
      {
        traverse(t->l);
        visit(t);
        traverse(t->r)
      }
    y--;
  }
 
traverse(struct node *t)
  {
    if (t != z)
      {
        visit(t);
        traverse(t->l);
        traverse(t->r);
      }
  }
 
traverse(struct node *t)
  {
   l: if (t == z) goto x;
      visit(t);
      traverse(t->l);
      t = t->r;
      goto l;
   x: ;
  }
 
traverse(struct node *t)
  {
   l: if (t == z) goto s;
      visit(t);
      stack.push(t); t = t->l; goto l;
   r: t = t->r; goto l;
   s: if (stack.empty()) goto x;
      t = stack.pop(); goto r;
   x: ;
  }
 
traverse(struct node *t)
  {
   l: while (t != z)
        {
          visit(t);
          stack.push(t->r); t = t->l;
        }
      if (stack.empty()) goto x;
      t = stack.pop(); goto l;
   x: ;
  }
 
traverse(struct node *t)
  {
    stack.push(t);
    while (!stack.empty())
      {
        t = stack.pop();
        while (t != z) 
          {  
            visit(t);
            stack.push(t->r); 
            t = t->l;
          }
      }
  }
 
traverse(struct node *t)
  {
    stack.push(t);
    while (!stack.empty())
      {
        t = stack.pop();
        if (t != z) 
          {  
            visit(t);
            stack.push(t->r); 
            stack.push(t->l);
          }
      }
  }
 
traverse(struct node *t)
  {
    stack.push(t);
    while (!stack.empty())
      {
        t = stack.pop(); visit(t);
        if (t->r != z) stack.push(t->r); 
        if (t->l != z) stack.push(t->l); 
      }
  }
 
 
--------------------------------
CHAPTER 6 Analysis of Algorithms 
 
 
--------------------------------
CHAPTER 7 Implementation of Algorithms 
 
 
--------------------------------
CHAPTER 8 Elementary Sorting Methods 
 
inline void swap(itemType a[], int i, int j)
  { itemType t = a[i]; a[i] = a[j]; a[j] = t; }
sort3(itemType a[], int N)
  {
    if (a[1] > a[2]) swap(a, 1, 2);
    if (a[1] > a[3]) swap(a, 1, 3);
    if (a[2] > a[3]) swap(a, 2, 3);
  }
const int maxN = 100;
main()
  {
    int N, i; itemType v, a[maxN+1];
    N = 0; while (cin >> v) a[++N] = v;
    a[0] = 0; 
    sort3(a, N);
    for (i = 1; i <= N; i++) cout << a[i] << ' ';
    cout << '\n';
  }
 
void selection(itemType a[], int N)
  { 
    int i, j, min;
    for (i = 1; i < N; i++)
      { 
        min = i;
        for (j = i+1; j <= N; j++) 
            if (a[j] < a[min]) min = j;
        swap(a, min, i);
      } 
  }
 
void insertion(itemType a[], int N)
  { 
    int i, j; itemType v;
    for (i = 2; i <= N; i++)
      { 
        v = a[i]; j = i;
        while (a[j-1] > v) 
          { a[j] = a[j-1]; j--; }  
        a[j] = v; 
      } 
  }
 
void bubble(itemType a[], int N)
  {
    int i, j;
    for (i = N; i >= 1; i--)
      for (j = 2; j <= i; j++)
        if (a[j-1] > a[j]) swap(a, j-1, j);
  }
 
void insertion(itemType a[], int p[], int N)
  { 
    int i, j; itemType v;
    for (i = 0; i <= N; i++) p[i] = i;
    for (i = 2; i <= N; i++)
      { 
        v = p[i]; j = i;
        while (a[p[j-1]] > a[v]) 
          { p[j] = p[j-1]; j--; }  
        p[j] = v; 
      } 
  }
 
void insitu(itemType a[], int p[], int N)
  { 
    int i, j, k; itemType t;
    for (i = 1; i <= N; i++) 
      if (p[i] != i)
        {
          t = a[i]; k = i;
          do
            { 
              j = k; a[j] = a[p[j]];
              k = p[j]; p[j] = j;
            }
          while (k != i);
          a[j] = t;
        } 
  }
 
void insertion(itemType a[], itemType *p[], int N)
  { 
    int i, j; itemType *v;
    for (i = 0; i <= N; i++) p[i] = &a[i];
    for (i = 2; i <= N; i++)
      { 
        v = p[i]; j = i;
        while (*p[j-1] > *v) 
          { p[j] = p[j-1]; j--; }
        p[j] = v; 
      } 
  }
 
void shellsort(itemType a[], int N)
  { 
    int i, j, h; itemType v;
    for (h = 1; h <= N/9; h = 3*h+1) ;
    for ( ; h > 0; h /= 3)
      for (i = h+1; i <= N; i += 1)
        { 
          v = a[i]; j = i;
          while (j>h && a[j-h]>v)
            { a[j] = a[j-h]; j -= h; }
          a[j] = v; 
        } 
  }
 
for (j = 0; j <  M; j++) count[j] = 0;
for (i = 1; i <= N; i++) count[a[i]]++;
for (j = 1; j <  M; j++) count[j] += count[j-1];
for (i = N; i >= 1; i--) b[count[a[i]]--] = a[i];
for (i = 1; i <= N; i++) a[i] = b[i];
 
 
--------------------------------
CHAPTER 9 Quicksort   
 
void quicksort(itemType a[], int l, int r)
  { 
    int i;
    if (r > l)
      { 
        i = partition(a, l, r);
        quicksort(a, l, i-1);
        quicksort(a, i+1, r);
      } 
  }
 
void quicksort(itemType a[], int l, int r)
  { 
    int i, j; itemType v;
    if (r > l)
      { 
        v = a[r]; i = l-1; j = r;
        for (;;)
          { 
            while (a[++i] < v) ;
            while (a[--j] > v) ;
            if (i >= j) break;
            swap(a, i, j);
          }
        swap(a, i, r);
        quicksort(a, l, i-1);
        quicksort(a, i+1, r);
      } 
  }
 
void quicksort(itemType a[], int l, int r)
  { 
    int i; Stack sf(50);
    for (;;)
      {
        while (r > l)
          { 
            i = partition(a, l, r);
            if (i-l > r-i)
              { sf.push(l); sf.push(i-1); l = i+1; }
            else
              { sf.push(i+1); sf.push(r); r = i-1; }
          } 
        if (sf.empty()) break;
        r = sf.pop(); l = sf.pop(); 
      }
  }
 
void select(itemType a[], int l, int r, int k)
  { 
    int i;
    if (r > l)
      { 
        i = partition(a, l, r);
        if (i > l+k-1) select(a, l, i-1, k);
        if (i < l+k-1) select(a, i+1, r, k-i);
      } 
  }
 
void select(itemType a[], int N, int k)
  { 
    int i, j, l, r; itemType v;
    l = 1; r = N;
    while (r > l)
      { 
        v = a[r]; i = l-1; j = r;
        for (;;)
          { 
            while (a[++i] < v) ;
            while (a[--j] > v) ;
            if (i >= j) break;
            swap(a, i, j);
          }
        swap(a, i, r);
        if (i >= k) r = i-1;
        if (i <= k) l = i+1;
      } 
  }
 
 
--------------------------------
CHAPTER 10 Radix Sorting  
 
class bitskey 
  {
    private:
      int x;
    public:
      bitskey& operator=(int i) 
          { x = i; return *this; }
      inline unsigned bits(int k, int j)
          { return (x >> k) & ~(~0 << j); }
  };
typedef bitskey itemType;
 
void radixexchange(itemType a[], int l, int r, int b)
  { 
    int i, j; itemType t;
    if (r>l && b>=0)
      { 
        i = l; j = r;
        while (j != i)
          { 
            while (!a[i].bits(b, 1) && ii) j--;
            swap(a, i, j);
          }
        if (!a[r].bits(b, 1)) j++;
        radixexchange(a, l, j-1, b-1);
        radixexchange(a, j, r, b-1);
      } 
  }
 
void straightradix(itemType a[], itemType b[], int N)
  {
    int i, j, pass, count[M-1];
    for (pass = 0; pass < w/m; pass++)
      {
        for (j = 0; j <  M; j++) count[j] = 0;
        for (i = 1; i <= N; i++) 
            count[a[i].bits(pass*m, m)]++;
        for (j = 1; j <  M; j++) 
            count[j] += count[j-1];
        for (i = N; i >= 1; i--)
            b[count[a[i].bits(pass*m, m)]--] = a[i];
        for (i = 1; i <= N; i++) a[i] = b[i];
      }
  }
 
 
--------------------------------
CHAPTER 11 Priority Queues  
 
class PQ
  {
    private:
      itemType *a;
      int N;
    public:
      PQ(int max) 
        { a = new itemType[max]; N = 0; }
     ~PQ()
        { delete a; }
      void insert(itemType v)
        { a[++N] = v; }
      itemType remove()
        {
          int j, max = 1; 
          for (j = 2; j <= N; j++)
            if (a[j] > a[max]) max = j;
          swap(a, max, N);
          return a[N--];
        }
  };
 
void PQ::upheap(int k)
  {
    itemType v;
    v = a[k]; a[0] = itemMAX;
    while (a[k/2] <= v)
      { a[k] = a[k/2]; k = k/2; }
    a[k] = v;
  }
void PQ::insert(itemType v)
  { a[++N] = v;  upheap(N); }
 
void PQ::downheap(int k)
  {
    int j; itemType v;
    v = a[k];
    while (k <= N/2)
      {
        j = k+k;
        if (j= a[j]) break;
        a[k] = a[j]; k = j;
      }
    a[k] = v;
  }
 
itemType PQ::remove()
  {
    itemType v = a[1];
    a[1] = a[N--];
    downheap(1);
    return v;
  }
 
itemType PQ::replace(itemType v)
  {
    a[0] = v;
    downheap(0);
    return a[0];
  }
 
void heapsort(itemType a[], int N)                           
  {
    int i; PQ heap(N);
    for (i = 1; i <= N; i++) heap.insert(a[i]);    
    for (i = N; i >= 1; i--) a[i] = heap.remove();    
  }
 
void heapsort(itemType a[], int N)
  {
    int k;
    for (k = N/2; k >= 1; k--) 
        downheap(a, N, k);
    while (N > 1)
      { swap(a, 1, N); downheap(a, --N, 1); }
  }
 
class PQ
  {
    private:
      itemType *a; int *p, *info;
      int N;
    public:
      PQ(int size)
        { a = new itemType[size]; 
          p = new int[size];
          info = new int[size]; N = 0; }
     ~PQ()
        { delete a; delete p; delete info; }
      void insert(int x, itemType v)
        { a[++N] = v; p[x] = N; info[N] = x; }
      void change(int x, itemType v)
        { a[p[x]] = v; }
      int remove() // remove smallest
        {
          int j, min = 1; 
          for (j = 2; j <= N; j++)
            if (a[j] < a[min]) min = j;
          swap(a, min, N); swap(info, min, N);
          p[info[min]] = min;
          return info[N--];
        }
      int empty()
        { return (N <= 0); }
  };
 
PQ::PQ(itemType *array, int size) 
  { 
    int k;
    p = new itemType[size]; q = new itemType[size]; 
    a = array; N = size; 
    for (k = 1; k <= N; k++) { p[k] = k; q[k] = k; }
    for (k = N/2; k >= 1; k--) downheap(k);
  }
 
void PQ::downheap(int k)
  {
    int j, v;
    v = p[k];
    while (k <= N/2)
      {
        j = k+k;
        if (j=a[p[j]]) break;
        p[k] = p[j]; q[p[j]] = k; k = j;
      }
    p[k] = v; q[v] = k;
  }
 
 
--------------------------------
CHAPTER 12 Mergesort   
 
i = 1; j = 1;
a[M+1] = itemMAX; b[N+1] = itemMAX;
for (k = 1; k <= M+N; k++)
  c[k] = (a[i]key <= b->key)
        { c->next = a; c = a; a = a->next; }
      else
        { c->next = b; c = b; b = b->next; }
    while (c != z);
    c = z->next; z->next = z;
    return c;
  }
 
void mergesort(itemType a[], int l, int r)
  {
    int i, j, k, m;
    if (r > l)
      {
        m = (r+l)/2;
        mergesort(a, l, m);  
        mergesort(a, m+1, r);
        for (i = m+1; i > l; i--) b[i-1] = a[i-1];
        for (j = m; j < r; j++) b[r+m-j] = a[j+1];
        for (k = l; k <= r; k++)
          a[k] = (b[i]next != z)
      {
        a = c; b = c->next->next->next;
        while (b != z)
          { c = c->next; b = b->next->next; }
        b = c->next; c->next = z;
        return merge(mergesort(a), mergesort(b));
      }
    return c;
  }
 
struct node *mergesort(struct node *c)
  {
    int i, N;
    struct node *a, *b, *head, *todo, *t;
    head = new node;
    head->next = c; a = z;
    for (N = 1; a != head->next; N = N+N) 
      {
        todo = head->next; c = head;
        while (todo != z)
          {
            t = todo; a = t; 
            for (i = 1; i < N; i++) t = t->next;
            b = t->next; t->next = z; t = b; 
            for (i = 1; i < N; i++) t = t->next;
            todo = t->next; t->next = z;
            c->next = merge(a, b);
            for (i = 1; i <= N+N; i++) c = c->next;
          }
      }
    return head->next;
  }
 
 
--------------------------------
CHAPTER 13 External Sorting  
 
 
--------------------------------
CHAPTER 14 Elementary Searching Methods 
 
class Dict
  {
    private:
      struct node
        { itemType key; infoType info; };
      struct node *a;
      int N;
    public:
      Dict(int max)
        { a = new node[max]; N = 0; }
     ~Dict()
        { delete a; }
      infoType search(itemType v);
      void insert(itemType v, infoType info);
  };
infoType Dict::search(itemType v) // Sequential 
  { 
    int x = N+1;
    a[0].key = v; a[0].info = infoNIL;
    while (v != a[--x].key) ;
    return a[x].info;
  }
void Dict::insert(itemType v, infoType info) 
  { a[++N].key = v; a[N].info = info; }
 
class Dict
 {
   private:
     struct node
       { itemType key; infoType info; 
         struct node *next; 
         node(itemType k, infoType i, struct node *n)
           { key = k; info = i; next = n; };
       };
     struct node *head, *z;
   public:
     Dict(int max) 
       {
         z = new node(itemMAX, infoNIL, 0);
         head = new node(0, 0, z);
       }
    ~Dict();
     infoType search(itemType v);
     void insert(itemType v, infoType info); 
 };
 
infoType Dict::search(itemType v) // Sorted list 
  {
    struct node *t = head;
    while (v > t->key) t = t->next;
    return (v = t->key) ? t->info : z->info;
  }
 
void Dict::insert(itemType v, infoType info) 
  {
    struct node *x, *t = head;
    while (v > t->next->key) t = t->next;
    x = new node(v, info, t->next); 
    t->next = x;
  }
 
infoType Dict::search(itemType v) // Binary search 
  { 
    int l = 1; int r = N; int x;
    while (r >= l)
      {
        x = (l+r)/2;
        if (v == a[x].key) return a[x].info;
        if (v <  a[x].key) r = x-1; else l = x+1;
      }
    return infoNIL;
  }
 
class Dict
  {
    private:
      struct node
        { itemType key; infoType info;
          struct node *l, *r; 
          node(itemType k, infoType i, 
               struct node *ll, struct node *rr)
            { key = k; info = i; l = ll; r = rr; };
        };
      struct node *head, *z;
    public:
      Dict(int max)
        { z = new node( 0, infoNIL, 0, 0);
          head = new node(itemMIN, 0, 0, z); }
     ~Dict();
      infoType search(itemType v);
      void insert(itemType v, infoType info);
  };
 
infoType Dict::search(itemType v) 
  {
    struct node *x = head->r;
    z->key = v;
    while (v != x->key)
      x = (v < x->key) ? x->l : x->r;
    return x->info;
  }
 
void Dict::insert(itemType v, infoType info) 
  {
    struct node *p, *x;
    p = head; x = head->r;
    while (x != z)
      { p = x; x = (v < x->key) ? x->l : x->r; }
    x = new node(v, info, z, z);
    if (v < p->key) p->l = x; else p->r = x;
  }
 
void Dict::treeprint(struct node *x)
  {
    if (x != z)
      {
        treeprint(x->l);
        printnode(x);
        treeprint(x->r);
      }
  }
 
void Dict::remove(itemType v)   
  {
    struct node *c, *p, *x, *t;
    z->key = v;
    p = head; x = head->r;
    while (v != x->key)
      { p = x; x = (v < x->key) ? x->l :  x->r; }
    t = x;
    if (t->r == z) x = x->l;
    else if (t->r->l == z) { x = x->r; x->l = t->l; }
    else
      {
        c = x->r; while (c->l->l != z) c = c->l;
        x = c->l; c->l = x->r;
        x->l = t->l; x->r = t->r;
      }
    delete t;
    if (v < p->key) p->l = x; else p->r = x;
  }
 
 
--------------------------------
CHAPTER 15 Balanced Trees  
 
void Dict::insert(itemType v, infoType info) 
  {
    x = head; p = head; g = head;
    while (x != z)
      { 
        gg = g; g = p; p = x; 
        x = (v < x->key) ? x->l :  x->r; 
        if (x->l->b && x->r->b) split(v);
      }
    x = new node(v, info, 1, z, z);
    if (v < p->key) p->l = x; else p->r = x;
    split(v); head->r->b = black;
  }
 
struct node *rotate(itemType v, struct node *y)
  {
    struct node *c, *gc;
    c = (v < y->key) ? y->l : y->r;
    if (v < c->key)
      { gc = c->l; c->l = gc->r; gc->r = c; }
    else
      { gc = c->r; c->r = gc->l; gc->l = c; }
    if (v < y->key) y->l = gc; else y->r = gc;
  return gc;
  }
 
void split(itemType v)
  {
    x->b = red; x->l->b = black; x->r->b = black;
    if (p->b)
      {
        g->b = red;
        if (vkey != vkey) p = rotate(v, g);
        x = rotate(v, gg);
        x->b = black;
      }
  }
 
      Dict(int max)
        { 
          z = new node( 0, infoNIL, black, 0, 0);
          z->l = z; z->r = z;
          head = new node(itemMIN, 0, black, 0, z); 
        }
 
 
--------------------------------
CHAPTER 16 Hashing   
 
unsigned stringkey::hash(int M)
  {
    int h; char *t = v;
    for (h = 0; *t; t++) 
        h = (64*h + *t) % M;
    return h;
  }
 
Dict::Dict(int sz)
  { 
    M = sz;
    z = new node; z->next = z; z->info = infoNIL;
    heads = new node*[M];
    for (int i = 0; i < M; i++) 
      { heads[i] = new node; heads[i]->next = z; }
  }
 
class Dict
  {
    private:
      struct node
        { itemType key; infoType info; 
          node() { key = " "; info = infoNIL; }
        };
      struct node *a;
      int M;
    public:
      Dict(int sz)
        { M = sz; a = new node[M]; }
      int search(itemType v);
      void insert(itemType v, infoType info)
        {
          int x = v.hash(M); 
          while (a[x].info != infoNIL) x = (x+1) % M;
          a[x].key = v; a[x].info = info; 
        }
  };
 
 
--------------------------------
CHAPTER 17 Radix Searching  
 
infoType Dict::search(itemType v) // Digital tree
  { 
    struct node *x = head;
    int b = itemType::maxb;
    z->key = v;
    while (v != x->key)
      x = (v.bits(b--, 1)) ? x->r : x->l;
    return x->info;
  }
 
void Dict::insert(itemType v, infoType info)
  {
    struct node *p, *x = head;
    int b = itemType::maxb;
    while (x != z)
      { 
        p = x; 
        x = (v.bits(b--, 1)) ? x->r : x->l; 
      }
    x = new node;
    x->key = v; x->info = info; x->l = z; x->r = z;
    if (v.bits(b+1, 1)) p->r = x; else p->l = x;
  }
 
infoType Dict::search(itemType v)  // Patricia tree 
  {
    struct node *p, *x;
    p = head; x = head->l;
    while (p->b > x->b)
      { 
        p = x; 
        x = (bits(v, x->b, 1)) ? x->r : x->l; 
      }
    if (v != x->key) return infoNIL;
    return x->info;
  }
 
void Dict::insert(itemType v, infoType info)
  {
    struct node *p, *t, *x;
    int i = maxb;
    p = head; t = head->l;
    while (p->b > t->b)
     { p = t; t = (bits(v, t->b, 1)) ? t->r : t->l; }
    if (v == t->key) return;
    while (bits(t->key, i, 1) == bits(v, i, 1)) i--;
    p = head; x = head->l;
    while (p->b > x->b  && x->b > i) 
     { p = x; x = (bits(v, x->b, 1)) ? x->r : x->l; }
    t = new node;
    t->key = v; t->info = info; t->b = i;
    t->l = (bits(v, t->b, 1)) ? x : t;
    t->r = (bits(v, t->b, 1)) ? t : x;
    if (bits(v, p->b, 1)) p->r = t; else p->l = t;
  }
 
 
--------------------------------
CHAPTER 18 External Searching  
 
 
--------------------------------
CHAPTER 19 String Searching  
 
int brutesearch(char *p, char *a)
  {
    int i, j, M = strlen(p), N = strlen(a);
    for (i = 0, j = 0; j < M && i < N; i++, j++)
      if (a[i] != p[j]) { i -= j-1; j = -1; }
    if (j == M) return i-M; else return i;
  }
 
int kmpsearch(char *p, char *a)
  {
    int i, j, M = strlen(p), N = strlen(a);
    initnext(p);
    for (i = 0, j = 0; j < M && i < N; i++, j++)
      while ((j >= 0) && (a[i] != p[j])) j = next[j];
    if (j == M) return i-M; else return i;
  }
 
initnext(char *p)
  {
    int i, j, M = strlen(p);
    next[0] = -1;
    for (i = 0, j = -1; i < M; i++, j++, next[i] = j)
      while ((j >= 0) && (p[i] != p[j])) j = next[j];
  }
 
int kmpsearch(char *a)
  {
    int i = -1;
sm: i++;
s0: if (a[i] != '1') goto sm; i++;
s1: if (a[i] != '0') goto s0; i++;
s2: if (a[i] != '1') goto s0; i++;
s3: if (a[i] != '0') goto s1; i++;
s4: if (a[i] != '0') goto s2; i++;
s5: if (a[i] != '1') goto s0; i++;
s6: if (a[i] != '1') goto s1; i++;
s7: if (a[i] != '1') goto s1; i++;
    return i-8;
  }
 
next[i] = (p[i] == p[j]) ? next[j] : j
 
int mischarsearch(char *p, char *a)
  {
    int i, j, t, M = strlen(p), N = strlen(a);
    initskip(p);
    for (i = M-1, j = M-1; j > 0; i--, j--)
      while (a[i] != p[j])
        {
          t = skip[index(a[i])];
          i += (M-j > t) ? M-j : t; 
          if (i >= N) return N;
          j = M-1;
        }
    return i;  
  }
 
const int q = 33554393;
const int d = 32;
int rksearch(char *p, char *a)
  {
    int i, dM = 1, h1 = 0, h2 = 0;
    int M = strlen(p), N = strlen(a);
    for (i = 1; i < M; i++) dM = (d*dM) % q;
    for (i = 0; i < M; i++) 
      {
        h1 = (h1*d+index(p[i])) % q;
        h2 = (h2*d+index(a[i])) % q;
      }
    for (i = 0; h1 != h2; i++)
      {
        h2 = (h2+d*q-index(a[i])*dM) % q;
        h2 = (h2*d+index(a[i+M])) % q;
        if (i > N-M) return N;
      }
    return i;
  }
 
 
--------------------------------
CHAPTER 20 Pattern Matching  
 
const int scan = -1;
int match(char *a)
  {
    int n1, n2; Deque dq(100);
    int j = 0, N = strlen(a), state = next1[0];
    dq.put(scan);
    while (state)
      {
        if (state == scan) { j++; dq.put(scan); }
        else if (ch[state] == a[j]) 
            dq.put(next1[state]);
        else if (ch[state] == ' ')
          {
            n1 = next1[state]; n2 = next2[state];
            dq.push(n1); if (n1 != n2) dq.push(n2);
          }
        if (dq.empty() || j==N) return 0; 
        state = dq.pop();
      }
    return j;
  }
 
 
--------------------------------
CHAPTER 21 Parsing   
 
expression()
  {  
    term();
    if (p[j] == '+') 
      { j++;  expression(); }
  }
 
term()
  {
    factor();
    if ((p[j] == '(') || letter(p[j])) term();
  }
 
factor()
  {
    if (p[j] == '(')
      {
        j++; expression();
        if (p[j] == ')') j++; else error();
      }
    else if (letter(p[j])) j++; else error();
    if (p[j] == '*') j++;
  }
 
expression
   term
      factor
         (
         expression
            term
               factor   A   *
               term
                  factor   B
            +
            expression
               term
                  factor   A
                  term
                     factor   C
         )
      term
         factor   D
                  
badexpression();
  {
    if (letter(p[j])) j++; else
      {
        badexpression();
        if (p[j] == '+') { j++; term(); }
        else error();
      }
  }

 
int expression()
  {  
    int t1,t2,r;
    t1 = term(); r = t1;
    if (p[j] == '+') 
      {
        j++; state++;
        t2 = state; r = t2; state++;
        setstate(t2, ' ', expression(), t1);
        setstate(t2-1, ' ', state, state);
      }
    return r;
  }
 
int term()
  {
    int t, r;
    r = factor();
    if ((p[j] == '(') || letter(p[j])) t = term();
    return r;
  }
 
int factor()
  {
    int t1, t2, r;
    t1 = state;
    if (p[j] == '(')
      {
        j++; t2 = expression();
        if (p[j] == ')') j++; else error();
      }
    else if (letter(p[j])) 
      {
        setstate(state, p[j], state+1, state+1);
        t2 = state; j++; state++;
      }
    else error();
    if (p[j] != '*') r = t2; else
      {
        setstate(state, ' ', state+1, t2);
        r = state; next1[t1-1] = state;
        j++; state++;
      }
    return r;
  }
 
void matchall(char *a)
  {
    j = 0; state = 1;
    next1[0] = expression();
    setstate(0, ' ', next1[0], next1[0]);
    setstate(state, ' ', 0, 0);
    while (*a) cout << match(a++) << ' '; 
    cout << '\n';
  }
 
 
--------------------------------
CHAPTER 22 File Compression  
 
  for (i = 0; i <= 26; i++) count[i] = 0;
  for (i = 0; i  <  M; i++) count[index(a[i])]++;
 
  for (i = 0; i <= 26; i++)
      if (count[i]) pq.insert(count[i], i);
  for ( ; !pq.empty(); i++)
    {
      t1 = pq.remove(); t2 = pq.remove();
      dad[i] = 0; dad[t1] = i; dad[t2] = -i;
      count[i] = count[t1] + count[t2];
      if (!pq.empty()) pq.insert(count[i], i); 
    }
 
for (k = 0; k <= 26; k++)
  {
    i = 0; x = 0; j = 1;
    if (count[k])
      for (t=dad[k]; t; t=dad[t], j+=j, i++)
        if (t < 0) { x += j; t = -t; }
    code[k] = x; len[k] = i;
  }
 
for (j = 0; j < M; j++)
    for (i = len[index(a[j])]; i > 0; i--)
        cout << ((code[index(a[j])] >> i-1) & 1);
 
 
--------------------------------
CHAPTER 23 Cryptology   
 
 
--------------------------------
CHAPTER 24 Elementary Geometric Methods 
 
struct point { int x, y; char c; };
struct line { struct point p1, p2; };
struct point polygon[Nmax];
 
int ccw(struct point p0, 
        struct point p1, 
        struct point p2 )
  {
    int dx1, dx2, dy1, dy2;
    dx1 = p1.x - p0.x; dy1 = p1.y - p0.y;
    dx2 = p2.x - p0.x; dy2 = p2.y - p0.y;
    if (dx1*dy2 > dy1*dx2) return +1;
    if (dx1*dy2 < dy1*dx2) return -1;
    if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
    if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) 
                                        return +1;
    return 0;
  }
 
int intersect(struct line l1, struct line l2)
  {
    return ((ccw(l1.p1, l1.p2, l2.p1)
            *ccw(l1.p1, l1.p2, l2.p2)) <= 0)
        && ((ccw(l2.p1, l2.p2, l1.p1)
            *ccw(l2.p1, l2.p2, l1.p2)) <= 0);
  }
 
float theta(struct point p1, struct point p2)
  {
    int dx, dy, ax, ay;
    float t;
    dx = p2.x - p1.x; ax = abs(dx);
    dy = p2.y - p1.y; ay = abs(dy);
    t = (ax+ay == 0) ? 0 : (float) dy/(ax+ay);
    if (dx < 0) t = 2-t; else if (dy < 0) t = 4+t;
    return t*90.0;
  }
 
int inside(struct point t, struct point p[], int N)
  {
    int i, count = 0, j = 0;
    struct line lt,lp;
    p[0] = p[N]; p[N+1] = p[1];
    lt.p1 = t; lt.p2 = t; lt.p2.x = INT_MAX;
    for (i = 1; i <= N; i++)
      {
        lp.p1= p[i]; lp.p2 = p[i];
        if (!intersect(lp,lt))
          {
            lp.p2 = p[j]; j = i;
            if (intersect(lp,lt)) count++;
          }
      }
    return count & 1;
  }
 
 
--------------------------------
CHAPTER 25 Finding the Convex Hull
 
int wrap(point p[], int N)
  {
    int i, min, M;
    float th, v;
    for (min = 0, i = 1; i < N; i++)
      if (p[i].y < p[min].y) min = i;
    p[N] = p[min]; th = 0.0;
    for (M = 0; M < N; M++)
      {
        swap(p, M, min);
        min = N; v = th; th = 360.0;
        for (i = M+1; i <= N; i++)
          if (theta(p[M], p[i]) > v)
            if (theta(p[M], p[i]) < th)
              { min = i; th = theta(p[M], p[min]); }
        if (min == N) return M;
      }
  }
 
int grahamscan(point p[], int N)
  {
    int i, min, M;
    for (min = 1, i = 2; i <= N; i++)
      if (p[i].y < p[min].y) min = i;
    for (i = 1; i <= N; i++)
      if (p[i].y == p[min].y)
        if (p[i].x > p[min].x) min = i;
    swap(p, 1, min);
    shellsort(p, N);
    p[0] = p[N];
    for (M = 3, i = 4; i <= N; i++)
      {
        while (ccw(p[M], p[M-1], p[i]) >= 0) M--;
        M++; swap(p, i, M);
      }
    return M;
  }
 
 
--------------------------------
CHAPTER 26 Range Searching  
 
int range(int v1, int v2)
  { return ranger(head->r, v1, v2); }
int ranger(struct node *t, int v1, int v2)
  {
    int tx1, tx2, count = 0;
    if (t == z) return 0;
    tx1 = (t->key >= v1);
    tx2 = (t->key <= v2);
    if (tx1) count += ranger(t->l, v1, v2);
    if (tx1 && tx2) count++;
    if (tx2) count += ranger(t->r, v1, v2);
    return count;
  }
 
class Range
  {
    private:
      struct node 
        { struct point p; struct node *next; };
      struct node *grid[maxG][maxG];
      struct node *z;
    public:
      Range();
      void insert(struct point p);
      int search(rect range);
  };
Range::Range()
  {
    int i, j;
    z = new node; 
    for (i = 0; i <= maxG; i++)
      for (j = 0; j <= maxG; j++)
          grid[i][j] = z;
  }
void Range::insert(struct point p)
  {
    struct node *t = new node;
    t->p = p; t->next = grid[p.x/size][p.y/size];
    grid[p.x/size][p.y/size] = t;
  }
 
int Range::search(struct rect range) // Grid method
 {
  struct node *t;
  int i, j, count = 0;
  for (i = range.x1/size; i <= range.x2/size; i++)
    for (j = range.y1/size; j <= range.y2/size; j++)
      for (t = grid[i][j]; t != z; t = t->next)
        if (insiderect(t->p, range)) count++;
  return count;
  }
 
class Range
  {
    private:
      struct node 
        { struct point p; struct node *l, *r; };
      struct node *z, *head;
      struct point dummy;
      int searchr(struct node *t, 
                      struct rect range, int d);
    public:
      Range();
      void insert(struct point p);
      int search(rect range);
  };
 
void Range::insert(struct point p) // 2D tree
  {
    struct node *f, *t; int d, td;
    for (d = 0, t = head; t != z; d !=d)
      {
        td = d ? (p.x < t->p.x) : (p.y < t->p.y);
        f = t; t = td ? t->l : t->r;
      }
    t = new node; t->p = p; t->l = z; t->r = z;
    if (td) f->l = t; else f->r = t;
  }
 
int Range::search(struct rect range) // 2D tree
  { return searchr(head->r, range, 1); }
int Range::searchr(struct node *t, 
                       struct rect range, int d)
 {
  int t1, t2, tx1, tx2, ty1, ty2, count = 0;
  if (t == z) return 0;
  tx1 = range.x1 < t->p.x; tx2 = t->p.x <= range.x2;
  ty1 = range.y1 < t->p.y; ty2 = t->p.y <= range.y2;
  t1 = d ? tx1 : ty1; t2 = d ? tx2 : ty2;
  if (t1) count += searchr(t->l, range, !d);
  if (insiderect(t->p, range)) count++;
  if (t2) count += searchr(t->r, range, !d);
  return count;
 }
 
 
--------------------------------
CHAPTER 27 Geometric Intersection  
 
Dict Xtree(Nmax), Ytree(Nmax);
struct line lines[Nmax];
int count = 0;
int intersections()
  {
    int x1, y1, x2, y2, N;
    for (N = 1; cin >> x1 >> y1 >> x2 >> y2; N++)
      {
        lines[N].p1.x = x1; lines[N].p1.y = y1;
        lines[N].p2.x = x2; lines[N].p2.y = y2;
        Ytree.insert(y1, N);
        if (y2 != y1) Ytree.insert(y2, N);
      }
    Ytree.traverse();
    return count;
  }
 
void Dict::visit(itemType v, infoType info)
  {
    int t, x1, x2, y1, y2;
    x1 = lines[info].p1.x; y1 = lines[info].p1.y;
    x2 = lines[info].p2.x; y2 = lines[info].p2.y;
    if (x2 < x1) { t = x2; x2 = x1; x1 = t; }
    if (y2 < y1) { t = y2; y2 = y1; y1 = t; }
    if (v == y1) 
        Xtree.insert(x1, info);
    if (v == y2)
      {
        Xtree.remove(x1, info);
        count += Xtree.range(x1, x2);
      }
  }
 
 
--------------------------------
CHAPTER 28 Closest-Point Problems  
 
int comp(struct node *t)
  { return (pass == 1) ? t->p.x : t->p.y; }
struct node *merge(struct node *a, struct node *b)
  {
    struct node *c; 
    c = z;
    do
      if (comp(a) < comp(b)) 
        { c->next = a; c = a; a = a->next; }
      else
        { c->next = b; c = b; b = b->next; }
    while (c != z);
    c = z->next; z->next = z;
    return c;
  }
 
check(struct point p1, struct point p2)
  {
    float dist;
    if ((p1.y != z->p.y) && (p2.y != z->p.y))
      {
        dist = sqrt((p1.x-p2.x)*(p1.x-p2.x)
                   +(p1.y-p2.y)*(p1.y-p2.y));
        if (dist < min)
          { min = dist; cp1 = p1; cp2 = p2; };
      }
  }
 
struct node *sort(struct node *c, int N)
  {
    int i;
    struct node *a, *b;
    float middle;
    struct point p1, p2, p3, p4;
    if (c->next == z) return c;
    a = c;
    for (i = 2; i <= N/2; i++) c = c->next;
    b = c->next; c->next = z;
    if (pass == 2) middle = b->p.x;
    c = merge(sort(a, N/2), sort(b, N-(N/2)));
    if (pass == 2)
      {
        p1 = z->p; p2 = z->p; p3 = z->p; p4 = z->p;
        for (a = c; a != z; a = a->next)
          if (fabs(a->p.x - middle) < min)
            {
              check(a->p, p1);
              check(a->p, p2);
              check(a->p, p3);
              check(a->p, p4);
              p1 = p2; p2 = p3; p3 = p4; p4 = a->p;
            }
      }
    return c;
  }
 
z = new node; z->p.x = max; 
              z->p.y = max; z->next = z;
h = new node; h->next = readlist();
min = max;
pass = 1; h->next = sort(h->next, N);
pass = 2; h->next = sort(h->next, N);
 
 
--------------------------------
CHAPTER 29 Elementary Graph Algorithms 
 
int V, E; 
int a[maxV][maxV];
 
void adjmatrix()
  {
    int j, x, y;
    cin >> V >> E;
    for (x = 1; x <= V; x++)
      for (y = 1; y <= V; y++) a[x][y] = 0;
    for (x = 1; x <= V; x++) a[x][x] = 1;
    for (j = 1; j <= E; j++)
      {
        cin >> v1 >> v2;
        x = index(v1); y = index(v2);
        a[x][y] = 1; a[y][x] = 1;
      }
  }
 
struct node
  { int v; struct node *next; };
int V, E;
struct node *adj[maxV], *z;
 
void adjlist()
  {
    int j, x, y; struct node *t;
    cin >> V >> E;
    z = new node;  z->next = z;
    for (j = 1; j <= V; j++) adj[j] = z;
    for (j = 1; j <= E; j++)
      {
        cin >> v1 >> v2;
        x = index(v1); y = index(v2);
        t = new node; 
          t->v = x; t->next = adj[y]; adj[y] = t;
        t = new node;
          t->v = y; t->next = adj[x]; adj[x] = t;
      }
  }
 
void search()
  {
    int k;
    for (k = 1; k <= V; k++) val[k] = unseen;
    for (k = 1; k <= V; k++) 
      if (val[k] == unseen) visit(k);
  }
 
void visit(int k) // DFS, adjacency lists
  {
    struct node *t;
    val[k] = ++id;
    for (t = adj[k]; t != z; t = t->next)
      if (val[t->v] == unseen) visit(t->v);
  }
 
void visit(int k) // DFS, adjacency matrix
  {
    int t;
    val[k] = ++id;
    for (t = 1; t <= V; t++) 
      if (a[k][t] != 0)
        if (val[t] == unseen) visit(t);
  }
 
Stack stack(maxV);
void visit(int k) // non-recursive DFS, adj lists
  {
    struct node *t;
    stack.push(k);
    while (!stack.empty())
      {
        k = stack.pop(); val[k] = ++id;
        for (t = adj[k]; t != z; t = t->next)
          if (val[t->v] == unseen) 
            { stack.push(t->v); val[t->v] = -1; }
      }
  }
 
Queue queue(maxV);
void visit(int k) // BFS, adjacency lists
  {
    struct node *t;
    queue.put(k);
    while (!queue.empty())
      {
        k = queue.get(); val[k] = ++id;
        for (t = adj[k]; t != z; t = t->next)
          if (val[t->v] == unseen) 
            { queue.put(t->v); val[t->v] = -1; }
      }
  }
 
 
--------------------------------
CHAPTER 30 Connectivity   
 
int visit(int k) // DFS to find articulation points
  {
    struct node *t; 
    int m, min;
    val[k] = ++id; 
    min = id;
    for (t = adj[k]; t != z; t = t->next)
      if (val[t->v] == unseen) 
        {
          m = visit(t->v);
          if (m < min) min = m;
          if (m >= val[k]) cout << name(k);
        }
      else if (val[t->v] < min) min = val[t->v];
    return min;
  }
 
class EQ
  {
    private:
      int *dad;
    public:
      EQ(int size);
      int find(int x, int y, int doit);
  };     
 
int EQ::find(int x, int y, int doit)
  { 
    int i = x, j = y;
    while (dad[i] > 0) i = dad[i];
    while (dad[j] > 0) j = dad[j];
    if (doit && (i != j)) dad[j] = i;
    return (i != j);
  }
 
int EQ::find(int x, int y, int doit)
  { 
    int t, i = x, j = y;
    while (dad[i] > 0) i = dad[i];
    while (dad[j] > 0) j = dad[j];
    while (dad[x] > 0) 
      { t = x; x = dad[x]; dad[t] = i; }
    while (dad[y] > 0) 
      { t = y; y = dad[y]; dad[t] = j; }
    if (doit && (i != j)) 
      if (dad[j] < dad[i])
        { dad[j] += dad[i] - 1; dad[i] = j; }
      else
        { dad[i] += dad[j] - 1; dad[j] = i; }
    return (i != j);
  }
 
 
--------------------------------
CHAPTER 31 Weighted Graphs  
 
PQ pq(maxV);
visit(int k) // PFS, adjacency lists
  {
    struct node *t;
    if (pq.update(k, -unseen) != 0) dad[k] = 0;
    while (!pq.empty())
      {
        id++; k = pq.remove(); val[k] = -val[k];
        if (val[k] == -unseen) val[k] = 0;
        for (t = adj[k]; t != z; t = t->next)
          if (val[t->v] < 0) 
            if (pq.update(t->v, priority))
              { 
                val[t->v] = -(priority); 
                dad[t->v] = k; 
              }
      }
  }
 
 
void kruskal()
 {
  int i, m, V, E;
  struct edge
    { char v1, v2; int w; };
  struct edge e[maxE];
  PQ pq(maxE); EQ eq(maxE);
  cin >> V >> E;
  for (i = 1; i <= E; i++)
      cin >> e[i].v1 >> e[i].v2 >> e[i].w;
  for (i = 1; i <= E; i++)
      pq.insert(i, e[i].w);
  for (i = 0; i < V-1; )
    {
      if (pq.empty()) break; else m = pq.remove(); 
      if (eq.find(index(e[m].v1),index(e[m].v2),1))
        { cout << e[m].v1 << e[m].v2 << ' '; i++; };
    }
 }
 
void search() // PFS, adjacency matrix
  {
    int k, t, min = 0;
    for (k = 1; k <= V; k++) 
      { val[k] = unseen; dad[k] = 0; }
    val[0] = unseen-1;
    for (k = 1; k != 0; k = min, min = 0)
      {
        val[k] = -val[k];
        if (val[k] == -unseen) val[k] = 0;
        for (t = 1; t <= V; t++)
          if (val[t] < 0)
            {
              if (a[k][t] && (val[t] < -priority))
                { val[t] = -priority; dad[t] = k; }
              if (val[t] > val[min]) min = t;
            }
        }
  }
 
 
--------------------------------
CHAPTER 32 Directed Graphs  
 
for (k = 1; k <= V; k++)
  {
    id = 0;
    for (j = 1; j <= V; j++) val[j] = 0;
    visit(k);
    cout >> '\n';
  }
 
for (y = 1; y <= V; y++)
  for (x = 1; x <= V; x++)
    if (a[x][y])
      for (j = 1; j <= V; j++)
        if (a[y][j]) a[x][j] = 1;
 
for (y = 1; y <= V; y++)
 for (x = 1; x <= V; x++) 
  if (a[x][y])
   for (j = 1; j <= V; j++) 
    if (a[y][j] > 0)
     if (!a[x][j] || (a[x][y]+a[y][j] < a[x][j]))
      a[x][j] = a[x][y] + a[y][j];
 
Stack stack(maxV);
int visit(int k) // DFS to find strong components
  {
    struct node *t; int m, min;
    val[k] = ++id; min = id;
    stack.push(k);
    for (t = adj[k]; t != z; t = t->next)
      {
        m = (!val[t->v]) ? visit(t->v) : val[t->v];
        if (m < min) min = m;
      }
    if (min == val[k])
      {
        do
          {
            m = stack.pop(); cout << m;
            val[m] = V+1;
          }
        while (m != k);
        cout << '\n';
      }
    return min;        
  }
 
 
--------------------------------
CHAPTER 33 Network Flow  
 
  priority = -flow[k][t];
  if (size[k][t] > 0) priority += size[k][t];
  if (priority > val[k]) priority = val[k];
 
for (;;)
  {
    if (!search(1,V)) break;
    y = V; x = dad[V];
    while (x != 0)
      {
        flow[x][y] = flow[x][y]+val[V];
        flow[y][x] = -flow[x][y];
        y = x; x = dad[y];
      }
  }
 
 
--------------------------------
CHAPTER 34 Matching   
 
for (m = 1; m <= N; m++)
  {
    for (s = m; s != 0;)
      {
        next[s]++; w = prefer[s][next[s]];
        if (rank[w][s] < rank[w][fiancee[w]])
          { t = fiancee[w]; fiancee[w] = s; s = t; }
      }
  }
 
 
--------------------------------
CHAPTER 35 Random Numbers  
 
a[0] = seed;
for (i = 1; i <= N; i++)
  a[i] = (a[i-1]*b+1) % m;
 
#include 
const int  m = 100000000;
const int m1 = 10000;
int mult(int p, int q)
  {
    int p1, p0, q1, q0;
    p1 = p/m1; p0 = p%m1;
    q1 = q/m1; q0 = q%m1;
    return (((p0*q1+p1*q0) % m1)*m1+p0*q0) % m;
  }
class Random
  {
    private:
      int a;
    public:
      Random(int seed)
        { a = seed; }
      int next()
        { const int  b = 31415821;
          a = (mult(a, b) + 1) % m; 
          return a; 
        }
  };
main()
  {
    int i, N; Random x(1234567);
    cin >> N;
    for (i = 1; i <= N; i++) 
        cout << x.next() << ' '; 
    cout << '\n';
  }

 
      int badnext(int r)
        { const int  b = 31415821;
          a = (mult(a, b) + 1) % m;
          return a % r;
        }
 
      int next(int r)
        { const int  b = 31415821;
          a = (mult(a, b) + 1) % m;
          return ((a/m1)*r)/m1;
        }
 
class Random
  {
    private:
      int a[55], j;
    public:
      Random(int seed);
      int next(int r)
        {
          j = (j+1) % 55;
          a[j] = (a[(j+23) % 55]+a[(j+54) % 55]) % m;
          return ((a[j]/m1)*r)/m1;
        }
  };
 
Random:: Random(int seed)
  { const int  b = 31415821;
    a[0] = seed;
    for (j = 1; j <= 54; j++)
    a[j] = (mult(a[j-1], b) + 1) % m;
  }
 
float chisquare(int N, int r)
  {
    int i, t, f[rmax]; Random x(1234567);
    for (i = 0; i < r; i++) f[i] = 0;
    for (i = 0; i < N; i++) f[x.next(r)]++;
    for (i = 0, t = 0; i < r; i++) t += f[i]*f[i];
    return (float) ((r*t/N) - N);
  }
 
 
--------------------------------
CHAPTER 36 Arithmetic   
 
for (i = 0; i < N; i++) r[i] = p[i]+q[i];
 
for (i = 0; i < 2*N-1; i++) r[i] = 0;
for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    r[i+j] += p[i]*q[j];
 
struct node *add(struct node *p, struct node *q)
  {
    struct node *t;
    t = z; z->c = 0;
    while ((p != z) && (q != z))
      {
        t->next = new node;
        t = t->next; t->c = p->c + q->c;
        p = p->next; q = q->next;
      }
    t->next = z; t = z->next; z->next = z;
    return t;
  }
 
struct node 
  { int c; int j; struct node *next; };
 
struct node *insert(struct node *t, int c, int j)
  {
    t->next = new node;
    t = t->next; t->c = c; t->j = j;
    return t;
  }
 
struct node *add(struct node *p, struct node *q)
  {
    struct node *t;
    t = z; z->c = 0; z->j = maxN;
    while ((p !=z) || (q != z))
      {
        if ((p->j == q->j) && ((p->c + q->c) != 0))
          {
            t = insert(t, p->c+q->c, p->j);
            p = p->next; q = q->next;
          }
        else if (p->j < q->j)
          { t = insert(t, p->c, p->j); p = p->next; }
        else if (q->j < p->j)
          { t = insert(t, q->c, q->j); q = q->next; }
      }
    t->next = z; t = z->next; z->next = z;
    return t;
  }
 
y = p[N];
for (i = N-1; i >= 0; i--) y = x*y + p[i];
 
float *mult(float p[], float q[], int N)
  {
    float pl[N/2], ql[N/2], ph[N/2], qh[N/2], 
          t1[N/2], t2[N/2];
    float r[2*N-2], rl[N], rm[N], rh[N];
    int i, N2;
    if (N == 1) 
      { r[0] = p[0]*q[0]; return (float *) r; }
    for (i = 0; i < N/2; i++)
      { pl[i] = p[i]; ql[i] = q[i]; }
    for (i = N/2; i < N; i++)
      { ph[i-N/2] = p[i]; qh[i-N/2] = q[i]; }
    for (i = 0; i < N/2; i++) t1[i] = pl[i]+ph[i];
    for (i = 0; i < N/2; i++) t2[i] = ql[i]+qh[i];
    rm = mult(t1, t2, N/2);
    rl = mult(pl, ql, N/2);
    rh = mult(ph, qh, N/2);
    for (i = 0; i < N-1; i++) r[i] = rl[i];
    r[N-1] = 0;
    for (i = 0; i < N-1; i++) r[N+i] = rh[i];
    for (i = 0; i < N-1; i++)
      r[N/2+i] += rm[i] - (rl[i]+rh[i]);
    return (float *) r;
  }
 
  for (i = 0; i < N; i++) 
    for (j = 0; j < N; j++)
      for (k = 0, r[i][j] = 0; k < N; k++) 
        r[i][j] += p[i][k]*q[k][j];
 
 
--------------------------------
CHAPTER 37 Gaussian Elimination  
 
for (i = 1;  i <= N; i++)
  for (j = i+1; j <= N; j++)
    for (k = N+1; k >= i; k--)
      a[j][k] -= a[i][k]*a[j][i]/a[i][i];
 
eliminate()
  {
    int i, j, k, max;
    float t;
    for (i = 1; i <= N; i++)
      {
        max = i;
        for (j = i+1; j <= N; j++)
          if (abs(a[j][i]) > abs(a[max][i])) max = j;
        for (k = i; k <= N+1; k++)
          { t = a[i][k]; 
                a[i][k] = a[max][k]; 
                          a[max][k] = t; }
        for (j = i+1; j <= N; j++)
          for (k = N+1; k >= i; k--)
            a[j][k] -= a[i][k]*a[j][i]/a[i][i];
      }
  }
 
substitute()
  {
    int j, k;
    float t;
    for (j = N; j >= 1; j--)
      {
        t = 0.0;
        for (k = j+1; k <= N; k++) t += a[j][k]*x[k];
        x[j] = (a[j][N+1]-t)/a[j][j];
      }
  }
 
    for (i = 1; i < N; i++)
      {
        a[i+1][N+1] -= a[i][N+1]*a[i+1][i]/a[i][i];
        a[i+1][i+1] -= a[i][i+1]*a[i+1][i]/a[i][i];
      }
    for (j = N; j >= 1; j--)
      x[j] = (a[j][N+1]-a[j][j+1]*x[j+1])/a[j][j];
 
 
--------------------------------
CHAPTER 38 Curve Fitting  
 
makespline(float x[], float y[], int N)
  {
    for (i = 2; i < N; i++) d[i] = 2*(x[i+1]-x[i-1]);
    for (i = 1; i < N; i++) u[i] = x[i+1]-x[i];
    for (i = 2; i < N; i++)
      w[i] = 6.0*((y[i+1]-y[i])/u[i]
                  -(y[i]-y[i-1])/u[i-1]);
    p[1] = 0.0; p[N] = 0.0;
    for (i = 2; i < N-1; i++)
      {
        w[i+1] = w[i+1] - w[i]*u[i]/d[i];
        d[i+1] = d[i+1] - u[i]*u[i]/d[i];
      }
    for (i = N-1; i > 1; i--)
      p[i] = (w[i]-u[i]*p[i+1])/d[i];
  }
 
float f(float x)
  { return x*x*x - x; }
float eval(float v)
  {
    float t; int i = 1;
    while (v > x[i+1]) i++;
    t = (v-x[i])/u[i];
    return t*y[i+1]+(1-t)*y[i] + 
        u[i]*u[i]*(f(t)*p[i+1]+f(1-t)*p[i])/6.0;
  }
 
for (i = 1; i <= M; i++) 
  for (j = 1; j <= M+1; j++) 
    {
      t = 0.0;
      for (k = 1; k <= N; k++) 
        t += f[i][k]*f[j][k];
      a[i][j] = t;
    }
 
 
--------------------------------
CHAPTER 39 Integration   
 
for (i = N; i > 0; i--) p[i] = p[i-1]/i; p[0] = 0;
 
double intrect(double a, double b, int N)
  {
    int i; double r = 0; double w = (b-a)/N;
    for (i = 1; i <= N; i++) r += w*f(a-w/2+i*w);
    return r;
  }
 
double inttrap(double a, double b, int N)
  {
    int i; double t = 0; double w = (b-a)/N;
    for (i = 1; i <= N; i++) 
      t += w*(f(a+(i-1)*w)+f(a+i*w))/2;
    return t;
  }
 
double intsimp(double a, double b, int N)
  {
    int i; double s = 0; double w = (b-a)/N;
    for (i = 1; i <= N; i++) 
      s += w*(f(a+(i-1)*w) + 
              4*f(a-w/2+i*w) + 
              f(a+i*w))/6;
    return s;
  }
 
double adapt(double a, double b)
  {
    double x = intsimp(a, b, 10);
    if (fabs(x - intsimp(a, b, 5)) > tolerance) 
      return adapt(a, (a+b)/2) + adapt((a+b)/2, b);
    return x;
   }
 
 
--------------------------------
CHAPTER 40 Parallel Algorithms  
 
 
--------------------------------
CHAPTER 41 The Fast Fourier Transform
 
eval(p, outN, 0);
eval(q, outN, 0);
for (i = 0; i <= outN; i++) r[i] = p[i]*q[i];
eval(r, outN, 0);
for (i = 1; i <= N; i++)
  { t = r[i]; r[i] = r[outN+1-i]; r[outN+1-i] = t; }
for (i = 0; i <= outN; i++) r[i] = r[i]/(outN+1);
 
eval(complex p[], int N, int k)
  {
    int i, j;
    if (N == 1)
      {
        p0 = p[k]; p1 = p[k+1];
        p[k] = p0+p1; p[k+1] = p0-p1;
      }
    else
      {
        for (i = 0; i <= N/2; i++)
          {
            j = k+2*i;
            t[i] = p[j]; t[i+1+N/2] = p[j+1];
          }
        for (i = 0; i <= N; i++) p[k+i] = t[i];
        eval(p, N/2, k);
        eval(p, N/2, (k+1+N)/2);
        j = (outN+1)/(N+1);
        for (i = 0; i <= N/2; i++)
          {
            p0 = w[i*j]*p[k+(N/2)+1+i];
            t[i] = p[k+i]+p0; 
            t[i+(N/2)+1] = p[k+i]-p0;
          }
        for (i = 0; i <= N; i++) p[k+i] = t[i];
      }
  }
 
 
--------------------------------
CHAPTER 42 Dynamic Programming  
 
for (j = 1; j <= N; j++)
  {
    for (i = 1; i <= M; i++)
      if (i >= size[j])
        if (cost[i] < cost[i-size[j]]+val[j])
          {
            cost[i] = cost[i-size[j]]+val[j];
            best[i] = j;
          }
  }
 
for (i = 1; i <= N; i++)
  for (j = i+1; j <= N; j++) cost[i][j] = INT_MAX;
for (i = 1; i <= N; i++) cost[i][i] = 0;
for (j = 1; j < N; j++)
  for (i = 1; i <= N-j; i++)
    for (k = i+1; k <= i+j; k++)
      {
        t = cost[i][k-1]+cost[k][i+j]
                             +r[i]*r[k]*r[i+j+1];
        if (t < cost[i][i+j])
          { cost[i][i+j] = t; best[i][i+j] = k; }
      }
 
order(int i, int j)
  {
    if (i == j) cout >> name(i); else
      {
        cout >> '(';
        order(i, best[i][j]-1); order(best[i][j], j);
        cout >> ')';
      }
  }
 
for (i = 1; i <= N; i++) 
  for (j = i+1; j <= N+1; j++) cost[i][j] = INT_MAX;
for (i = 1; i <= N; i++) cost[i][i] = f[i];
for (i = 1; i <= N+1; i++) cost[i][i-1] = 0;
for (j = 1; j <= N-1; j++)
  for (i = 1; i <= N-j; i++)
    {
      for (k = i; k <= i+j; k++)
        {
          t = cost[i][k-1]+cost[k+1][i+j];
          if (t < cost[i][i+j])
            { cost[i][i+j] = t; best[i][i+j] = k; }
        }
      for (k = i; k <= i+j; cost[i][i+j] += f[k++]) ;
    }
 
 
--------------------------------
CHAPTER 43 Linear Programming  
 
pivot(int p, int q)
  {
    int j, k;
    for (j = 0; j <= N; j++)
      for (k = M+1; k >= 1; k--)
        if (j!=p && k!=q)
          a[j][k] = a[j][k]-a[p][k]*a[j][q]/a[p][q];
    for (j = 0; j <= N; j++) 
      if (j != p) a[j][q] = 0;
    for (k = 1; k <= M+1; k++) 
      if (k != q) a[p][k] = a[p][k]/a[p][q];
    a[p][q] = 1;
  }
 
for (;;)
  {
    for (q = 0; (q<=M+1) && (a[0][q]>=0); q++) ;
    for (p = 0; (p<=N+1) && (a[p][q]<=0); p++) ;
    if (q>M || p>N) break;
    for (i = p+1; i <= N; i++)
      if (a[i][q] > 0)
        if (a[i][M+1]/a[i][q] < a[p][M+1]/a[p][q]) 
          p = i;
    pivot(p,q);
  }
 
 
--------------------------------
CHAPTER 44 Exhaustive Search  
 
visit(int k)
  { 
    int t;
    val[k] = ++id;
    for (t = 1; t <= V; t++)
      if (a[k][t])
        if (val[t] == 0) visit(t);
    id--; val[k] = 0;
  }
 
visit(int k)
  {
    int t;
    val[k] = ++id;
    if (id == V) writeperm();
    for (t = 1; t <= V; t++)
      if (val[t] == 0) visit(t);
    id--; val[k] = 0;
  }
 
 
--------------------------------
CHAPTER 45 NP-Complete Problems