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.
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[c_num] := x; c[c_num] := y; b[x] := false; b[y] := false; End; End; Writeln(c_num); For i := 1 to C_num do Begin Writeln(c[i],' ',c[i]); End; END.
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)?
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.
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 ?
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?
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).
AFAIK, Fastest biparite matching algorithm - Hopcroft Carp, with complexity E*sqrt(V); V-num 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.