Discussion @ 1022. Genealogical Tree @ Timus Online Judge

The right idea

Posted by VladG 24 Oct 2002 21:22

Nice problem!
To solve it your needto use the topological sort on the graph (DAG).
It can be done with DFS algorithm.

Re: The right idea

Posted by compiler 27 Apr 2005 21:24

Actually I just sorted twice(one ascending and another one descending) and got AC.

Re: The right idea

Posted by Akshin Salimov 27 Apr 2005 21:50

Your(compiler) idea is interesting, but not clear to me.
Can you tell me your idea in details plz?

You can also make this via e-mail: akshinioi@yahoo.com

Edited by author 27.04.2005 21:52

Re: The right idea

Posted by Vitaliy_Ivashchenko 28 Aug 2007 03:37

VladG is right. It's the topological sort problem.

See Cormen, Leiserson, Rivest, Stein "Introduction to algorithms" -> Elementary algorithms for graphs -> Topological sort

Re: The right idea

Posted by №Ⅰ——ＹＤＷ 28 Apr 2009 11:42

In favor of

Re: The right idea

Posted by dxtdxt 8 May 2010 20:07

The idea doesn't seem to be so clear.

Discussion of Problem 1022. Genealogical Tree