ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1077. Travelling Tours

I use greedy method to choose loop in the order of DFS.But I've just found a peculiar test case that DFS will be incorrect.Is greedy method right here?
Posted by Huang Yizheng 22 Oct 2001 17:56
For example:
7 10
1 2
2 3
2 4
2 5
3 5
4 5
5 6
5 7
6 7
1 7
At first the DFS procedure find the loop:
(1,2,3,5,6,7,1),then it'll find (1,2,3,5,7,1).
and next,no loop with unused edge will be found!?!
In fact,the maximum T is 3(it's obvious),but use greedy
method + DFS the number of T only reach 2.
Unless we regulated the order of search
(it means DFS can't be right!),otherwise we have to
delete a found loop to let more loop to have unused
edge,then how to make the regulations?
Re: I use greedy method to choose loop in the order of DFS.But I've just found a peculiar test case that DFS will be incorrect.Is greedy method right here?
Posted by Tran Nam Trung (trungduck@yahoo.com) 22 Oct 2001 20:33
Sorry, for this example, the correct output is T = 4 !!!
Check your algorithm again !!!
mailto : trungduck@yahoo.com

> For example:
> 7 10
> 1 2
> 2 3
> 2 4
> 2 5
> 3 5
> 4 5
> 5 6
> 5 7
> 6 7
> 1 7
> At first the DFS procedure find the loop:
> (1,2,3,5,6,7,1),then it'll find (1,2,3,5,7,1).
> and next,no loop with unused edge will be found!?!
> In fact,the maximum T is 3(it's obvious),but use greedy
> method + DFS the number of T only reach 2.
> Unless we regulated the order of search
> (it means DFS can't be right!),otherwise we have to
> delete a found loop to let more loop to have unused
> edge,then how to make the regulations?
>
>
Re: I use greedy method to choose loop in the order of DFS.But I've just found a peculiar test case that DFS will be incorrect.Is greedy method right here?
Posted by Denis Koshman 2 Aug 2008 00:11
Once DFS loop is found, it ALWAYS contains unused edge - e.g. the edge which looped it in :)
Re: I use greedy method to choose loop in the order of DFS.But I've just found a peculiar test case that DFS will be incorrect.Is greedy method right here?
Posted by twinsclover 17 Oct 2010 13:10

Edited by author 17.10.2010 13:22

Edited by author 17.10.2010 13:22