Cod sursa(job #1585099)

Utilizator iondodon1998Dodon Ion iondodon1998 Data 30 ianuarie 2016 19:19:57
Problema Sortare topologica Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.71 kb
Program TopologicalSort;
type
	lista=^datelista;
	celula=^datecelula;
	datelista=record
		nr:longint;
		next,pred:lista;
	end;
	datecelula=record
		 a,x,z:lista;
		 tmp:boolean;
	end;
graf=array[1..50000] of celula;
var t:graf;
		a,x,z:lista;
		n,m:longint;
		f1,f2:text;

Procedure initieregraf;
	var i:longint;
	begin
		for i:=1 to n do
			begin
  			new(t[i]);
				new(t[i]^.x);
				t[i]^.x^.nr:=-1;
				t[i]^.x^.next:=nil;
				t[i]^.a:=t[i]^.x;
				t[i]^.z:=t[i]^.x;
				t[i]^.tmp:=false;
			end;
	end;

Procedure citiredate;
	var i,a,b:longint;
	begin
		for i:=1 to m do
			begin
				readln(f1,a,b);
				new(t[a]^.x);
				t[a]^.x^.nr:=b;
				t[a]^.x^.next:=nil;
				t[a]^.z^.next:=t[a]^.x;
				t[a]^.z:=t[a]^.x;
			end;
	end;

Procedure adsol(i:longint);
	begin
		new(x);
		x^.nr:=i;
		x^.next:=nil;
		x^.pred:=z;
		z^.next:=x;
		z:=x;
	end;

Procedure visit(i:longint);
	begin
		t[i]^.tmp:=true;
    t[i]^.x:=t[i]^.a^.next;
    while (t[i]^.x<>nil) do 
    	begin
    		if t[t[i]^.x^.nr]^.tmp=false then
    			visit(t[i]^.x^.nr);
    		t[i]^.x:=t[i]^.x^.next;
    	end;
		adsol(i);
	end;


Procedure tpsort;
	var i:longint;
	begin
		new(x);
		x^.nr:=-1;
		x^.next:=nil;
		x^.pred:=nil;
		a:=x;
		z:=x;
		for i:=1 to n do
			if t[i]^.tmp=false then
				visit(i);
	end;

Procedure afisarerezultat;
	begin
		x:=z;
		while (x^.nr<>-1) do 
			begin
				write(f2,x^.nr,' ');
				x:=x^.pred;
			end;
	end;


Procedure main;
	begin
		readln(f1,n,m);
		initieregraf;
		citiredate;
		tpsort;
		afisarerezultat;
	end;


begin
	assign(f1,'sortare.in'); reset(f1);
	assign(f2,'sortare.out'); rewrite(f2);
	main;
	close(f1);
	close(f2);
end.