First of all I suppose the graph is a tree (M=N-1 and all vertices are connected, see the text). Is it a tree? I choose one vertex (let it be 1) and consider it as root. I perform breadth first algorithm starting from the root and obtain vertices in increasing order of distances (in the same time I obtain the parent for each vertex). The result is the array C[1..N]. From N downto 1 I search for available C[i] and P[C[i]] (P[C[i]] is the parent for C[i]). I mark C[i] and P[C[i]] not to be used furthermore (unavailable). The edge [C[i],P[C[i]] is part of solution

and the final result is WA on test 7...
what's wrong ?

Edited by author 15.11.2005 20:32

The algorithm was correct but I ignored the output format  ... AC now

Hi,

I have the same problem with WA #7, in what way was the output format wrong?