Any hints or tests? I have WA 30, what did you do to AC? Ok, I got AC after lots of WA 30 attempts by iterating over the input in the reversed order, which makes no sense to me. My current best guess is that test #30 is broken, so there are at least two correct answers and it accepts only one of them as correct. Of course, my algo can delete edges in different order depending on the order in which it iterates over them, but I'm pretty sure it always removes the maximum number of edges. 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. Try such test... :) 4 3 2 3 1 2 3 4 Correct answer is 2 1 2 3 4 I don't think, that greedy is a good idea... Try this one 4 3 1 2 1 3 3 4 Correct Answer: 2 1 2 3 4 Я получил АС! Сложность 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 I have WA 30 too((( What did you do to AC? New tests were added. All solutions were rejuded. 260 authors have lost AC. The most common verdict was Runtime error (stack overflow). I just add to my code #pragma comment(linker, "/STACK:66777216") and get AC =) I sent more tests for TLE. Your tests were added. AC solutions were rejudged. 30 authors lost AC 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? OK, I have no idea how could I possibly come up with such solution and how come it passed the tests before :P 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 The answer is: 5 1 2 4 8 5 9 3 6 7 11 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 nondelete, 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. here is example: 8 7 1 2 2 3 3 4 3 5 4 7 7 8 5 6 Answer depends on the way you go from city 3. Yes. But your algorithm probably realy work wrong. My greedy: While graph is not empty 1. We choose any vertex v: deg(v)=1 (e=(v,u)) 2. Add to the answer edge e. 3. Delete v and u with all its edges from the graph. @Burunduk1 I used the same greedy algorithm as u did but I get WA#2, can u please help me? Edited by author 24.07.2013 17:16 First of all I suppose the graph is a tree (M=N1 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? 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 Your test was added, 15 authors lost AC. 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? You need only 2 DFS. This solution get AC in 0.08s. 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(maxflow) so N*N(because it's tree). I got AC using bipartite matching :) I'm too  HopcroftCarp rulezz=) i use dynamic progrmaming and got AC in O(N), i think the best the algo too find maximum biprate matching ue O(nm), what's your algo????? sorry for y poor english. AFAIK, Fastest biparite matching algorithm  Hopcroft Carp, with complexity E*sqrt(V); Vnum of vertices; E  num of edges; Given graph is a tree, so it's possible to color it into 2 colors, after that, take all black vertices as one part, white as other part and find max matching between them. I can't give strict evidence of this approach but it intuitively understandable  just draw sample output on the paper and everything will become clear=) You can see my code > i shared my account here http://acm.timus.ru/forum/thread.aspx?id=25749&upd=634266195834002500 Just look my submission. this algo is very similar to Dinica algorithm, are they identical? ну, не знаю даже! Кун прошел за 0.9 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. the answer needs to cover the all vertex ? Edited by author 15.02.2009 18:10 
