Given a list of people and a parent-child relation, find the tallest family trees.
The input file consists of a list of people ids and a list of pairs
The list of pairs indicates the parent-child relation, e.g.
means that person with id
1 is the parent of person with id
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.
Here is a Ruby implementation.
Want to read more?
I regularly write solutions to programming problems that you may or may not find in technical job interviews. I also love to explain those solutions and 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.