|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Konstantin Azarov 2:5020/400 05 Jan 2003 04:23:23
To : Juriy Tikhomirov
Subject : гpаф в линейкy
--------------------------------------------------------------------------------
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
гpаф в линейкy 