UVa 615

From Algorithmist

1. include <stdio.h>

struct NodeNum {

   int num;
   NodeNum *next;

}; NodeNum *node_num_list = 0;

struct Edge {

   int from, to;
   Edge *next;
   Edge(int f, int t);

}; Edge *edge_list;

void ClearNodeNumList() {

   NodeNum *p = node_num_list, *q;
   while (p) {
       q = p;
       p = p->next;
       delete q;
   }
   node_num_list = new NodeNum;
   node_num_list->next = 0;
   node_num_list->num = -42;

}

int GetNodeNum(int n) {

   NodeNum *p = node_num_list;
   int c = 0;
   while (p->next) {
       p = p->next;
       if (p->num == n) return c;
       c++;
   }
   p->next = new NodeNum;
   p = p->next;
   p->num = n;
   p->next = 0;
   return c;

}

int NumNodes() {

   NodeNum *p = node_num_list->next;
   int c = 0;
   while (p) {
       c++; p = p->next;
   }
   return c;

}

Edge::Edge(int f, int t) {

   from = GetNodeNum(f);
   to = GetNodeNum(t);

}

int NumEdgesTo(Edge *p, int node_no) {

   int c = 0;
   while (p) {
       if (p->to == node_no) c++;
       p = p->next;
   }
   return c;

}

void Visit(Edge *edge_list, int node, int visited[]) {

   Edge *p = edge_list;
   visited[node]++;
   while (p) {
       if (p->from == node) {
           Visit(edge_list, p->to, visited);
       }
       p = p->next;
   }

}

int IsATree(Edge *edge_list) {

   int n_nodes = NumNodes();
   int i, root_node = -1;
   int n_edges_to;

   if (n_nodes == 0) return 1;

   for (i=0; i<n_nodes; i++) {
       n_edges_to = NumEdgesTo(edge_list, i);
       if (n_edges_to == 0) {
           if (root_node == -1) {
               root_node = i;
           } else {
               return 0;
           }
       } else if (n_edges_to != 1) {
           return 0;
       }
   }
   if (root_node == -1) return 0;

   int *visited = new int[n_nodes];
   for (i=0; i<n_nodes; i++) visited[i] = 0;

   Visit(edge_list, root_node, visited);

   for (i=0; i<n_nodes; i++) {
       if (visited[i] != 1) {
           delete[]visited;
           return 0;
       }
   }

   delete[]visited;
   return 1;

}

int main() {

   int case_no = 1;
   int from, to;
   FILE *inf = stdin;

   while (fscanf(inf, "%d %d", &from, &to), from != -1 || to != -1) {

       edge_list = 0;
       ClearNodeNumList();

       while (from || to) {
           Edge *new_edge = new Edge(from, to);
           new_edge->next = edge_list;
           edge_list = new_edge;
           fscanf(inf, "%d %d", &from, &to);
       }

       int is_tree = IsATree(edge_list);
       printf("Case %d is %sa tree.\n", case_no++, is_tree ? "" : "not ");

       while (edge_list) {
           Edge *e = edge_list;
           edge_list = edge_list->next;
           delete e;
       }
   }
   return 0;

}