Redundancy Problem: Solution Using Circular Queue

#include < fstream.h >
#include < iostream.h >
#include < stdlib.h >
#include < stdio.h >

int max (int a, int b) { if (a < b) return b; else return a; }

void intdisplay(void *t) { cout << *(int *)t << " "; }

class Array
{
public:
  Array(int r, int c)
  {
     int i;
     rows=r;
     cols=c;
     array = new int[r*c];
     for (i=0 ; i < r*c ; i++) array[i] = 0;
  }
  Array(int c)
  {
     int i;
     rows=1;
     cols=c;
     array = new int[c];
     for (i=0 ; i < c ; i++) array[i] = 0;
  }
  int  get(int i, int j)
  {
     if (i < 0 || i > rows) return 0;
     if (j < 0 || j > cols) return 0;
     return array[i*cols+j];
  }
  int get(int i)
  {
     if (i < 0 || i > cols) return 0;
     return array[i];
  }
  void put(int i, int j, int k)
  {
     if (i > = 0 && i < = rows && j > = 0 && j < = cols) array[i*cols+j] = k;
  }
  void put(int i, int k)
  {
     if (i > = 0 && i < = cols) array[i] = k;
  }
  ~Array() { delete array; }

private:
  int rows;
  int cols;
  int *array;
};

class Cell
{
friend class Queue;
public:
   Cell(void *ptr, Cell *lst)
   {
      item = ptr;
      next = lst;
   }
private:
   void *item;
   Cell *next;
};

class Queue
{
public:
   Queue(void (* d)(void *)) { dispfn = d; tail = NULL;  }
   Queue() { dispfn = intdisplay; tail = NULL;  }
   void  enqueue(void *t)
   {
      Cell *h;
      if (t == NULL) return;
      
      if (tail == NULL)
      {
         tail = new Cell(t, NULL);
         tail->next = tail;
      }
      else
      {
         h = new Cell(t, tail->next);
         tail->next = h;
         tail = h;
      }
   }
   void *dequeue()
   {
      if (tail == NULL) return NULL;
      Cell *ptr = tail->next;
      void *t = ptr->item;
      if (ptr != tail)
         tail->next = ptr->next;
      else
         tail = NULL;
      delete ptr;
      return t;
   }
   void display()
   {
     Cell *t;
     if (tail == NULL) { cout << "(empty)\n";  return; }
     for (t=tail->next ; t != tail ; t=t->next) (dispfn)(t->item);
     (dispfn)(tail->item);
     printf("\n");
   }
   int   empty()  {  return tail == NULL;  }
private:
   Cell *tail;
   void (* dispfn)(void *);
};

class City
{
public:
   City (int c, int p) { cty=c; prnt=p; }
   int parent()  { return prnt; }
   int city()    { return cty; }
private:
   int cty;
   int prnt;
};

/***-------------------------------------------------***/
/*** Redundancy:                                     ***/
/***   Input: A network (n by n array of 0-1 values) ***/
/***          A number of cities (n above)           ***/
/***   Output: 1 if network is redundant             ***/
/***           0 otherwise                           ***/
/*** Checks network links for redundant connections  ***/
/***-------------------------------------------------***/
int redundancy(Array *links, int cities)
{
   Queue *s = new Queue();
   Array *visited = new Array(cities+1);
   City  *current;
   int i;

   s->display();
   s->enqueue(new City(0,-1));
   s->display();
   while (!s->empty())
   {
      current = (City *)s->dequeue();
      s->display();
      if (visited->get(current->city())) continue;
      visited->put(current->city(), 1);
      for (i=0 ; i < = cities ; i++)
      {
         if (!links->get(current->city(),i) || current->city() == i) continue;
         if (!visited->get(i))
	 {
            s->enqueue(new City(i, current->city()));
            s->display();
	 }
         else
         if (i != current->parent()) return 1;
      }
   }
   return 0;
}

#define MAX_CITIES 200

int main(int argc, char **argv)
{
   Array *links = new Array(MAX_CITIES, MAX_CITIES);
   char *buffer = new char[128];
   int city1, city2, cost, cities=0;

   if (argc != 2) exit(0);
   fstream fin(argv[1], ios::in);
   while (fin.getline(buffer, 128, '\n'))
   {
      sscanf(buffer, "%d%d", &city1, &city2);
      links->put(city1,city2,1);
      cities = max(max(cities, city1), city2);
   }
   fin.close();

   printf("((%d))\n",redundancy(links,cities));

   return 1;
}