ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Common Board

Topological Sort
Posted by Manolache Adrian 29 Jul 2004 13:34
{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.