|
|
back to boardI 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? 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? 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? 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?
Edited by author 17.10.2010 13:22
Edited by author 17.10.2010 13:22 |
|
|
