Network Redundacy (Finding Cycles in a Graph)

(see also the Java solution)

#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 Stack;
public:
   Cell(void *ptr, Cell *lst)
   {
      item = ptr;
      next = lst;
   }
private:
   void *item;
   Cell *next;
};

class Stack
{
public:
   Stack(void (* d)(void *)) { dispfn = d; head = NULL; }
   Stack() { dispfn = intdisplay; head = NULL; }
   void  push(void *t)
   {
      Cell *ptr;
      if (t == NULL) return;
      Cell *h = new Cell(t, head);
      head = h;
   }
   void *pop()
   {
      if (head == NULL) return NULL;
      void *ptr = head;
      void *t = head->item;
      head = head->next;
      delete ptr;
      return t;
   }
   void display()
   {
     if (head == NULL) { cout << "(empty)\n";  return; }
     for (Cell *t=head ; t != NULL ; t=t->next) (dispfn)(t->item);
     printf("\n");
   }
   int   empty()  {  return head == NULL;  }
private:
   Cell *head;
   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)
{
   Stack *s = new Stack();
   Array *visited = new Array(cities+1);
   City  *current;
   int i;

   s->push(new City(0,-1));
   while (!s->empty())
   {
      current = (City *)s->pop();
      while (!s->empty() && visited->get(current->city()))
         current=(City *)s->pop();
      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->push(new City(i, current->city()));
         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;
}