Nevermind. Solved.

I've detected my error with this input:

11 10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 9
6 10
7 11

5 roads can be blocked.

Edited by author 29.08.2011 22:33

После того как сайт проверил мою задачу, я решил проверить несколько частных случаев
и в одном у меня программа ломалась, но это не помешало ей пройти проверку.
Входные данные:
5 4
1 2
2 3
3 4
4 5
Ответ 2 и 23 и 45, но должно быть 2 и 12 и 45

Any hints or tests?

You guys have to sort the roads to be the same sequence as the input
means first input,first output

9 8
1 2
1 6
1 8
1 3
1 4
4 5
1 7
7 9
Answer:
3
7 9
1 2
4 5

I used greedy search on sorted edges in increasing order of sum of degrees of vertices (of edge). Should I refine my compare function? Other hints?

Please help me, what is wrong with my solution....
Const
 MaxN = 100000;
Var
 b : array[1..MaxN] of boolean;
 c : array[1..2,1..MaxN] of longint;
 c_num,n,m,i,x,y : longint;
BEGIN
 Readln(n,m);
 Fillchar(b,sizeof(b),true);
 Fillchar(c,sizeof(c),0);
 c_num := 0;
 For i := 1 to m do
  begin
   Read(x,y);
   if b[x] and b[y] then
    Begin
     Inc(c_num);
     c[1][c_num] := x;
     c[2][c_num] := y;
     b[x] := false;
     b[y] := false;
    End;
  End;
 Writeln(c_num);
 For i := 1 to C_num do
  Begin
   Writeln(c[1][i],' ',c[2][i]);
  End;
END.

Я получил АС! Сложность O(N+M)=O(2N). Стандартный обход в глубину, но несколько изменённый. Важно что-то заметить про висячие вершинки.

Edited by author 07.07.2015 00:02

Edited by author 07.07.2015 00:02

Edited by author 07.07.2015 00:02

Can you give me some TEST  i have WA 30. Thank you

New tests were added. All solutions were rejuded. 260 authors have lost AC. The most common verdict was Runtime error (stack overflow).

Hi, I had an accepted solution 3 years ago and now I have no idea what was wrong/right. Looking at my previous solution that now gets TLE, it was Kuhn matching algorithm. Did the constraints change or did you just add better tests?

I take the list (any City with 1 road) and delete this road, then going to connected city and mark all road from it as non-delete, then  i going to near city and repeat first step.
For example
5 4
1 2
2 3
3 4
3 5
Start with 1 City, delete (1 2) then go in 3 city, and remove (3 4) or (3 5)?

Why WA2 ?
Sorry fo my English.

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

Please check my submission 4323013. It gets AC although to the input
4 3
1 2
2 4
4 3

it answers
1
2 4

when the right answer is clearly
2
1 2
3 4

Greetings!
I have just solved this problem with DP on a tree via DFS, but it appeared to be much too slow (0.25s), though I expected a better result. There's a tree in this problem, so totally solution must be O(N).
May any precial tricks be there or I just did something wrong?

what does it mean?

is it possible to find biparite matching for n or n logn?
if we divide graph into 2 parts  - maximal matching is the answer. But biparite matching founding time is NM(max-flow) so N*N(because it's tree).

Please, add test, where N=100 000, and graph is a line. It will cause stack overflow (at least for my solution).

I use greedy algo, but I got WA :( Please give some useful tests.