Discussion @ 1077. Travelling Tours @ Timus Online Judge

I know the agorithm, but who can prove it? starforever 11 Jan 2007 06:49

let N be the node num of the graph.
so why the maximum cycle number is M-N+1?
where M is the edge num.

please...

Re: I know the agorithm, but who can prove it? starforever 11 Jan 2007 08:09

o, sorry, I made a mistake...

Re: I know the agorithm, but who can prove it? Archit 11 Jan 2007 11:30

is ur problem solved

Re: I know the agorithm, but who can prove it? Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 11 Jan 2007 14:59

The correct formula is M-N+K, where K is the number of connected components of given graph. Why is not the question, if you know algo of building all these cycles...

Re: I know the agorithm, but who can prove it? Chmel_Tolstiy 15 Apr 2008 00:38

Great hint. Thanks.

Re: I know the agorithm, but who can prove it? Tom 13 Oct 2022 14:57

Edited by author 13.10.2022 15:00

Edited by author 13.10.2022 15:00

Discussion of Problem 1077. Travelling Tours