Discussion @ 1077. Travelling Tours @ Timus Online Judge

I know the agorithm, but who can prove it?

Posted by 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?

Posted by StarForever 11 Jan 2007 08:09

o, sorry, I made a mistake...

Re: I know the agorithm, but who can prove it?

Posted by Archit 11 Jan 2007 11:30

is ur problem solved

Re: I know the agorithm, but who can prove it?

Posted by Vedernikoff Sergey 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?

Posted by Chmel_Tolstiy 15 Apr 2008 00:38

Great hint. Thanks.

Re: I know the agorithm, but who can prove it?

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