|
|
|
|
|
|
|
Вернуться
| 1 qwertyuiop, 05 июля 2010 г. 8:58:25 | |
|
Всем спасибо) примерно понял)
|
|
|
| 2 Михнович Иван Вадимович, 05 июля 2010 г. 2:02:21 | |
Каждой вершине графа сопоставляешь переменную, длиной в один байт. Обнуляешь её для каждой вершины. Выбираешь стартовую вершину и от неё обходишь граф в глубину, при этом при посещении каждой вершины присваиваешь её новой переменной значение 1 или 2 (поочерёдно - для стартовой - 1, для всех соседних - 2, для всех соседей соседних стартовой - снова 1 и .т.д). Перед присваиванием проверяешь - является ли значением новой переменной 0. Если нет, и если её значение отличается от того, что ты собирался присвоить - то цикл нечётной длины существует.
Нарисуй на бумаге, сразу поймешь в чём фокус.
|
|
|
| 3 qwertyuiop, 04 июля 2010 г. 23:02:43 | |
|
Можно по подробнее , что значит красить граф в два цвета?
|
|
|
| 4 Панявин Михаил [HKL], 04 июля 2010 г. 20:49:52 | |
|
Там нужно красить граф в два цвета при обходе в глубину, если при поиске в глубину пришли в вершину покрашеную в первый цвет а нам нужно её красить во второй то значит есть цикл нечётной длины.
|
|
|
| 5 qwertyuiop, 04 июля 2010 г. 20:38:30 | |
|
Народ, подскажите как определить, есть ли в графе цикл нечетной длины?
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
