[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение теории
Author Message
Dmitriy Kravtsov

Topics: 6
Messages: 6

My Profile
Здравствуйте, Михаил Семенович!

Нашел в вашей книге ошибку: не работает алгоритм к задаче "Is it a tree?".

И не работает она вот на таком тесте:

1 2
4 5
4 6
5 6
0 0
-1 -1

Выдает "Case 1 is a tree", хотя на самом деле граф несвязный и содержит цикл.
Mihail Dolinskiy

Topics: 1556
Messages: 36794

My Profile
Спасибо за информацию.
Не ошибается только тот, кто ничего не делает.
Надеюсь, моя ошибка не помешала тебе сдать эту задачу.
Vadim Zaharenko

Topics: 16
Messages: 51

My Profile
Здравствуйте! Зачем в книге в теме "Минимальное остовное дерево" при решении задач методом Крускала вводить массив Rank, ведь это бесcмысленная трата сложности алгоритма и затрачиваемой памяти? Без него программа работает так же, и процедура Link пердельно упрощается.
Procedure Link(x,y : longint);
  begin
    pred[y]:=x; {или pred[x]:=y;}
  end;

Mihail Dolinskiy

Topics: 1556
Messages: 36794

My Profile
Так КРИТИЧЕСКИ всегда и нужно относится к информации.
Нет предела совершенству.
Молодец
Dmitriy Gorbatovskiy

Topics: 1
Messages: 9

My Profile
Она ускоряет поиск корня множества
 
Forum Index ->Олимпиадное программирование ->Обсуждение теории
Time:0,109