ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Общий форум

Topological Sort
Послано Manolache Adrian 29 июл 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.