Discussion @ 1198. Jobbery @ Timus Online Judge

Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Posted by Alexey 9 Jun 2006 11:55

subj

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Posted by Samsonov Alex [USU] 9 Jun 2006 12:28

Try to use cash.

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Posted by Anton [SUrSU#6] 9 Jun 2006 14:34

Why cash?
More explanations may be?

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Posted by Vitalik 9 Jun 2006 14:54

At me too a problem on 21 test.

Please, Help to solve this problem

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Posted by Alexey 9 Jun 2006 17:59

What do U mean "cash"? How to do it?
Will it be quicker?
Thanks.

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Posted by shrek 23 Nov 2006 10:14

It's obviously a directed graph. We find its strongly-connected-components. Now if one of the vertices in one component satisfies the problem the other vertices in its component do. so we merge each component into one vertex. the remaining graph is a DAG (directed acyclic graph). the component which its in-degree is zero is the answer. and if there are more than one component with in-degree==zero then we have no answer because the graph is not connected.

Discussion of Problem 1198. Jobbery