|
|
вернуться в форумОбщий форумTopological Sort {Same algorithm like for problem Genealogical Tree(Volume 1) but time I got Wrong Anwer 7 I used an array of lists allocated dinamicaly from 1 to n: the i-th lists holds the subject(s) that must be studied before subject i or nil(NULL) For every subject i in the given configuration to verify, I check if it's list is empty or not. This looks like this: for (i=1; i<=n; i++) { if (list[config[i]]=NULL) 1. it's not empty (there are subject's that must be examined before this one) so output NO else 2. if the list is empty then eliminate this subject from all of the list's } for i:=1 to n do begin if (list[config[i]]==nil) 1. it's not empty (there are subject's that must be examined before this one) so output NO else 2. if the list is empty then eliminate this subject from all of the list's end;
} Here is the Pascal source {Wrong answer 7} type pnod=^nod; nod=record next:pnod; val:longint; end; var i,n,m,s,u,subject:longint; nou,now:pnod; list:array[1..1000] of pnod; procedure Elim(valo:longint); var i:longint; prev:pnod; begin for i:=1 to n do if list[i]<>nil then begin if list[i]^.val=valo then begin list[i]:=list[i]^.next; end else begin prev:=list[i]; now:=list[i]^.next; while now<>nil do begin if now^.val=valo then begin prev^.next:=now^.next; break; end; prev:=now; now:=now^.next; end; end; end; end; begin read(n,m); for i:=1 to n do list[i]:=nil; for i:=1 to m do begin readln(s,u); new(nou); nou^.next:=list[u]; nou^.val:=s; list[u]:=nou; end; for i:=1 to n do begin read(subject); if list[subject]<>nil then begin writeln('NO'); halt; {Successufully Terminated!?.< -> The power of halt} end; Elim(subject); end; writeln('YES'); end. |
|
|