error in the code given in skiena's book for the application of dfs to find a cycle in a graph

Question

This is the code for dfs.

bool processed[MAXV+1]; /* which vertices have been processed */
bool discovered[MAXV+1]; /* which vertices have been found */
int parent[MAXV+1]; /* discovery relation */  
#define MAXV 1000 /* maximum number of vertices */

typedef struct {
int y;                   /* adjacency info */
int weight;             /* edge weight, if any */
struct edgenode *next; /* next edge in list */
} edgenode;

typedef struct {
edgenode *edges[MAXV+1]; /* adjacency info */
int degree[MAXV+1];     /* outdegree of each vertex */
int nvertices;         /* number of vertices in graph */
int nedges;            /* number of edges in graph */
bool directed;        /* is the graph directed? */
} graph;

dfs(graph *g, int v)
{

   edgenode *p;           /* temporary pointer */
   int y;                /* successor vertex */
   if (finished) return; /* allow for search termination */
   discovered[v] = TRUE;
   time = time + 1;
   entry_time[v] = time;
   process_vertex_early(v);
   p = g->edges[v];
   while (p != NULL) {
         y = p->y;
         if (discovered[y] == FALSE) 
         {
             parent[y] = v;
             process_edge(v,y);
             dfs(g,y);
         }
         else if ((!processed[y]) || (g->directed))
         process_edge(v,y);
         if (finished) return;

       p = p->next;

}
   process_vertex_late(v);
   time = time + 1;
   exit_time[v] = time;
   processed[v] = TRUE;
}

And for finding the cycles it has modified the process edge function like below

process_edge(int x, int y)
{
    if (parent[x] != y) { /* found back edge! */
       printf("Cycle from %d to %d:",y,x);
    find_path(y,x,parent);
    printf("\n\n");
    finished = TRUE;
    }
}

Now imagine a small tree with just 2 leaf nodes and one root. When this tree is subjected to this function, I believe it will say that it has cycles. which is wrong !! Please correct me if i am wrong. Thanks.

Answer 1

From the errata corrige, at http://www.cs.sunysb.edu/~skiena/algorist/book/errata:

(*) Page 173, process_edge procedure -- the correct test should be

if (discovered[y] && (parent[x] != y)) { /* found back edge */

Answer 2

I think you're right, and the code is wrong.

It looks to me like the problem is if (parent[x] != y) in process_edge(). In both calls to process_edge(), the supposed parent is passed before the supposed child, i.e. inside process_edge() we expect x to be the parent, so I think that line should be if (parent[y] != x).