|
|
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 |
|
|