076 Drumuri

[•domino]

Aici puteţi discuta despre problema Drumuri.

[•Pharaoh]

Am implementat o sursa la subiectul asta si din pacate nu iau decat 0 puncte, deoarece se pare ca algoritumul meu nu gaseste celui de-al doilea nod un nod cu care sa creeze pereche (a se citi muchie);
adica returneaza la un moment dat in raspuns ceva de genul: x y 0.

imi aduc aminte ca am implementat o data o sursa (dupa ce am scris-o pe cea mai recenta mi-am adus aminte ) care dadea aceeasi greseala

Ideea algoritmului este urmatoarea:
Fac un fel de DFS, dar numai pe 2 nivele: drumul ar arata cam asa x->y->z; stiind x; afisez si dupa aceea scad gradul la toate 3;
Daca are cineva timp sa se uite pe sursa mea si sa-mi spuna unde greseste i-as fi recunoscator pt asta:

Cod:

type mat=array[1..10000,1..10000]of byte;
var a:mat;
	nrt,n,m,i,j,v0,v1,v2:longint;
 	f:text;


procedure readdata;
var f:text;
	na,nb,i,j:longint;
begin
assign(f,'drumuri.in'); reset(f);
readln(f,n,m);
if odd(m) then begin writedata; halt; end
else

	for i:=1 to m do begin readln(f,na,nb); a[na,nb]:=1; a[nb,na]:=1;
    					   inc(a[na,na]); inc(a[nb,nb]); 	
    end;

close(f);
end;

procedure dfs(x:longint);
var i,j:longint;
begin
for i:=1 to n do
    if (a[x,i]=1)and(v0<>i)and(v1<>i)
    	then
         begin
           if v1=0 then begin
           				v1:=i;
                        for j:=1 to n do
                          if (a[v1,j]=1)and(v0<>j)and(v1<>j) then
                          begin
                          		v2:=j;
                                exit;
                          end;
                        end;

         end;
end;

Begin
assign(f,'drumuri.out'); rewrite(f);
readdata;
writeln(f,'1');
for i:=1 to n do
	if nrt=m/2 then break
    else
	while a[i,i]<>0 do begin
    					v0:=i; v1:=0; v2:=0;
    					dfs(i);
                        writeln(f,v0,' ',v1,' ',v2);
                        a[v0,v1]:=0; a[v1,v0]:=0;
                        a[v1,v2]:=0; a[v2,v1]:=0;
                        dec(a[v0,v0]);
                        dec(a[v1,v1]); dec(a[v1,v1]);
                        dec(a[v2,v2]);
                        nrt:=nrt+1;
    end;
close(f);
End.

Am scris sursa in Pascal, ca Rhide (sau djgpp; care o fi ) nu-mi merge si nu am folosit alocare dinamica pt ca nu prea sunt un mare fan al ei.

Raspunsurile pt sursa:

Cod:

Test 	Timp executie 	Memorie folosita 	Mesaj 	Punctaj/test
1	176ms	4940kb	Paznicul are ruta cu noduri invalide: 172 507 0.	0
2	228ms	5608kb	Paznicul are ruta cu noduri invalide: 33 320 0.	0
3	260ms	6456kb	Paznicul are ruta cu noduri invalide: 165 379 0.	0
4	276ms	7536kb	Paznicul are ruta cu noduri invalide: 118 651 0.	0
5	396ms	9180kb	Paznicul are ruta cu noduri invalide: 110 1346 0.	0
6	588ms	11576kb	Paznicul are ruta cu noduri invalide: 108 229 0.	0
7	876ms	15460kb	Paznicul are ruta cu noduri invalide: 164 951 0.	0
8	1020ms	22968kb	Time limit exceeded.	0
9	296ms	39976kb	Paznicul are ruta cu noduri invalide: 155 3477 0.	0
10	176ms	66000kb	Memory limit exceeded.	0
Punctaj total	0

PS: Multam' anticipat