Due: Monday, April 4th, 2011 9:10am

Read a directed graph from standard input, where the graph is encoded as lines of numbers. Each line represents a node, where the first number is the “name” of the node, and each subsequent represent an edge from the node to a different node (i.e., the one named by the number).

For example,

1 2 3 2 3 4 3 4 4 1

represents the main graph example from the slides, where `1` is “A”,
`2` is “B”, etc.

You can assume that each line before an EOF in the input has at
least one number, that at least one line is provided,
that the numbers are all positive and fit into a C
`int` type, that the numbers on one line are space-separated, and that
the nodes are numbered consecutively starting from `1`.

You can use readnums.h and
readnums.c to handle all of the parsing. You can
either use the array-of-arrays result of `read_num_lines()` directly as the
representation of a graph, or you can convert it into a
different representation of the graph.

After reading in a representation of a graph, have your program print two results:

- Print
`"yes\n"`if all nodes in the graph are reachable by following edges from the node represented by the*first*line of the input,`"no\n"`if not. - Print
`"yes\n"`if all nodes in the graph are reachable by following edges from the node represented by the*last*line of the input,`"no\n"`if not.

You can use any data structure that we have developed during the semester, but note that all nodes are given consecutive numbers as names, which makes “hashing” on the name particularly easy.

Some extra test inputs:

all reachable from first? | all reachable from last? | |

list | yes | no |

cycle | yes | yes |

wide | yes | no |

triple | yes | yes |

Have your program print a third result: a number indicating the
maximum required to reach any node from the first one. For example,
the number is `2` for the example from the slides.

Some extra test inputs:

max depth | |

list | 99999 |

cycle | 99999 |

wide | 1 |

triple | 14289 |

Last update: Thursday, April 7th, 2011mflatt@cs.utah.edu |