гpаф в линейкy

From

Konstantin Azarov ()

To

Juriy Tikhomirov

Date

2003-01-05T03:23:23Z

Area

RU.ALGORITHMS

From: "Konstantin Azarov" <azarov@comtv.ru>

Hello, Juriy!

 JT> такая задачка:
 JT> есть соответствия символов:
 JT> 1<2,2<4,4<3,7<3,11<1,5<4,5<3
 JT> необходимо выстpоить в линейкy в символы, yчитывая соответствия:
 JT> 11, 1, 2, 5, 4, 7, 3

Очень просто :): строим по исходным символам направленный граф (это понятно
как). Потом начинаем обход в глубину, храня при этом глобальную переменную -
"текущую позицию" (t). Эта переменная ведет себя так: сначала она равна
единице. После того как мы рассмотрели текущую вершину, присваиваем позиции
этой вершины значение t, а t увеличиваем на 1. Тогда после окончания обхода
в глубину будет выполняться следующее свойство: если вершина i достижима из
j, то t[i]<t[j], а поскольку 1<=t[k]<=N, значит t[k] и есть позиции вершин в
нашем отсортированном списке.

 JT> кста, поясните особый смысл циклических списков.
А что в них такого особого? Берем линейный список и конец связываем с
началом :)

--- ifmail v.2.15dev5
 * Origin: Comcor-TV (2:5020/400)