Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/14: Рейтинг темы: голосов - 14, средняя оценка - 4.86
Jumbo
0 / 0 / 0
Регистрация: 06.05.2011
Сообщений: 19
1

Топологическая сортировка графа

06.05.2011, 19:07. Просмотров 2718. Ответов 10
Метки нет (Все метки)

Написал программу топологически сортирующую граф с помощью обхода в ширину. Сдал её на информатиксе (http://http://informatics.mccme.ru/m...hapterid=166#1), нормально приняло (правда там малоые ограничения вершин и дуг). Сдаю задачу на других тестах, где вершин до 100000 и дуг до 100000 и получаю Runtime error. Никак не пойму почему, вроде алгоритм правильный.
Код
program topsort;

{$APPTYPE CONSOLE}

uses
  SysUtils;
const maxN=100009;maxM=100009;
var f,f1                    :text;
    head,col,top            :array[0..maxN] of integer;
    dest,next               :array[0..maxM] of integer;
    n,m,i,u,v,k             :integer;


procedure add(u,v:integer);
begin
 if head[u]=0 then begin
  dest[0]:=dest[0]+1;
  head[u]:=dest[0];
  dest[dest[0]]:=v;
  exit;
 end;
 dest[0]:=dest[0]+1;
 dest[dest[0]]:=v;
 next[dest[0]]:=head[u];
 head[u]:=dest[0];
end;



procedure dfs(u:integer);
var i:integer;
begin
 col[u]:=1;{серая}

 i:=head[u];
 if i>0 then begin
  repeat
   if col[dest[i]]=0 then dfs(dest[i]);
   if col[dest[i]]=1 then begin write(f1,'-1'); close(f1); halt end;
   i:=next[i];
  until i=0;
 end;

 top[k]:=u;  inc(k);
 col[u]:=2;{чёрная}
end;



begin
 reset(f,'topsort.in');
 rewrite(f1,'topsort.out');
 read(f,n,m);
 for i:=1 to m do begin
  read(f,u,v);
  add(u,v);
 end;{считывание}
 close(f);

 k:=1;
 for i:=1 to n do begin
  if col[i]=0 then dfs(i);
  if k=n+1 then break;
 end;
  {формирование массива TOP - обратный порядок выхода из вершин}

  for i:=n downto 1 do write(f1,top[i],' ');

 close(f1);

end.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.05.2011, 19:07
Ответы с готовыми решениями:

Задача топологическая сортировка графа
Добрый вечер,предположим задан взвешенный,ориентированный,ациклический граф в виде матрицы...

Неверно работает топологическая сортировка
Привет. Я написал топологическую сортировку, решил проверить на тестовом примере его, но оно не...

Топологическая сортировка графа
Здравствуйте! Помогите, пожалуйста. Пишу программу для поиска путей на графах между всеми парами...

Топологическая сортировка графа
Задали задание, неделю пытаюсь сделать и все никак не выходит, топологическая сортировка из книгу...

Топологическая сортировка графа
Здравствуйте, у меня есть код сортировки, но он слишком громоздкий, помогите его сделать более...

10
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
06.05.2011, 19:12 2
Погенерируйте большие тесты, позапускайте свою прогу на них.
0
Jumbo
0 / 0 / 0
Регистрация: 06.05.2011
Сообщений: 19
06.05.2011, 19:16  [ТС] 3
В том то и дело, что я генерирую и генерирую, а ошибок всё нет..
На тестах с вершинами 100000 и столько же ребер работает тоже..
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
06.05.2011, 19:49 4
Возможно, не хватает стека. Увеличьте и попробуйте отправить.
0
06.05.2011, 19:49
Jumbo
0 / 0 / 0
Регистрация: 06.05.2011
Сообщений: 19
06.05.2011, 19:50  [ТС] 5
Извините, что и как увеличить (я знаю что такое стек, но не понял)?
Вы имеете в виду увеличить размерность массивов?
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
06.05.2011, 19:54 6
DFS с 100000 вершин хавает много стека. Возможно, в тестирующей системе его размер ограничен, и происходит RE, а у вас на компьютере нет. Увеличьте размер стека с помощью директивы {$M}.
Например {$M10000000} для 10 МБ.
0
Jumbo
0 / 0 / 0
Регистрация: 06.05.2011
Сообщений: 19
06.05.2011, 20:07  [ТС] 7
Security violation на 1 тесте
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
06.05.2011, 20:12 8
Скоко поставили? Поменьше попробуйте.
0
Jumbo
0 / 0 / 0
Регистрация: 06.05.2011
Сообщений: 19
06.05.2011, 20:23  [ТС] 9
{$M 2047483646}
У меня работает нормально так, а там ошибка
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
06.05.2011, 20:30 10
Вы два гигабайта взять пытаетесь
Поставьте например половину ограничения по памяти задачи.
1
Jumbo
0 / 0 / 0
Регистрация: 06.05.2011
Сообщений: 19
06.05.2011, 20:33  [ТС] 11

Приняло, спасибо огромное!
0
06.05.2011, 20:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.05.2011, 20:33

Топологическая сортировка
Здорова! Тут от вычитал новое понятие "топологическая сортировка". Вообщем есть задачка нужно...

Топологическая сортировка
Ошибка в строке 34, подскажите как исправить: 'reverse' was not declared in this scope //...

топологическая сортировка
Добрый вечер. Мне необходимо провести топологическую сортировку к отношению на мн-ве(см....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru