Given a list of people and a parent-child relation, find the tallest family trees.

Input. The input file consists of a list of people ids and a list of pairs [parent, child]. The list of pairs indicates the parent-child relation, e.g. [1,2] means that person with id 1 is the parent of person with id 2.

The first line of input consists of a sequence of integers separated by a single space, the list of people ids. The remaining lines consist each of a pair of integers separated by a single space, the parent-child relation. The input is terminated by an EOF character.

The following is an sample input file.

Output. The output consists of all the roots of the tallest family trees, sorted. The roots are to be given in a single line, separated by a single space.

For example, the following is the output for the previous sample input.

Solution

Here is a Ruby implementation.

I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every month. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.