Some hint about this problem.

Posted by

Y.Y.M. 13 Jun 2004 10:14

1. If we regard the start airport as the root,it is clear that the graph is a tree.

2. If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win.

3. We use a flag to record start from one airport will win or not.Just DFS to obtain all flag.

In this way,you could get AC in O(e).

Is there any better way to solve this problem?

I think the answer is yes.

So,could you write down your thought?

Re: Some hint about this problem.

Posted by

begi 11 Jan 2015 11:03

I didn't want to create new thread, so I will just revive this thread.

My idead was to use simple minimax algorithm:

boolean firstWins(node v)

for every neighbour u of node v check secondWins(u)

return true if for some u second loses

return false

boolean secondWins(node v)

for every neighbour u of node v check firstWins(u)

return true if for some u first loses

return false

Hope it will be helpful to someone.

*Edited by author 11.01.2015 11:04*