Как достроить ориентированный граф минимальным количеством рёбер, чтобы с любой вершины можно было добраться до любой другой вершины?
Как достроить ориентированный граф минимальным количеством рёбер, чтобы с любой вершины можно было добраться до любой другой вершины?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
| Название |
|---|



По идее так:
1) Найдем компоненты сильной связности.
2) Возьмем какую-то одну компоненту и будем из какой-то ее вершины строить по 2 ребра в вершину каждой другой компоненты(одно ребро из компоненты, другое- в компоненту).
Благодаря этому из каждой компоненты можно будет добраться в каждую(через ту, что мы выбрали на шаге 2), а так как внутри компонент можно попасть в любую вершину, граф действительно станет связным.
В каждую не нужно, достаточно в одну.
Почему?
Допустим у нас есть несколько компонент, между которыми нет ни одного ребра. И что нам даст опускание в одну из них?
Извиняюсь, неправильно понял сначала. Но все равно таким образом оптимально не получится.
Это не всегда правильно, допустим у нас есть пустой граф из 5 вершин, тогда выгоднее сделать цикл из 5 вершин и рёбер, а по этому алгоритму у нас получится точно не 5 :)
Не, глупость сморозила. Не работает в общем случае.
А, если граф не обязательно связный, можно зациклить не связанные компоненты, и этот цикл со всем содержимым сам станет 1 компонентой.
Пусть у нас есть граф из 2n вершин, что ребро из i-той вершины в j-тую в нём есть тогда и только тогда, когда i принадлежит отрезку [1, n], а j отрезку [n + 1, 2n]. Очевидно, что достаточно n рёбер из (i + n)-той вершины в i-тую при i из отрезка [1, n]. Вашему алгоритму, если я не ошибаюсь, нужно 2n - 1 рёбер (в графе n стоков и n истоков).
Да, то что описано выше работает только для слабо связного графа. Коммент выше тоже не поможет без доработки.
Какая-то непростая задача, а откуда она?
В универе задали
А, ну так и решай сам) Это тебе не бесплатная онлайн-помощь отстающим.
А такой вариант может подойдет? 1) Найдем компоненты сильной связности 2) Сделаем цикл из этих компонент, т.е. по очереди из первой в N-ую компоненту проведем ребра. Возьмем в каждой компоненте любую вершину в которую будет входить ребро из i — 1 компоненты и выходить в i + 1 компоненту. Поправьте, если что не так)
Вот как сделать цикл и есть вопрос, там просто уже расставлены ребра, которые могут помочь, нашему будущему циклу
Известная задача. Как-то хотел перевод сюда запилить, но руки не дошли
http://www.springer.com/cda/content/document/cda_downloaddocument/9780387235288-c2.pdf
Вроде бы ответ — это максимум из кол-ва компонент, в которые ничто не входит и из которых ничего не выходит. Ну и понятно, ка строить ответ тогда
Ответ правильный.
И как же?
Хм, наврал, нахаляву не получатся :(
Эта задачу я в первый раз увидел на тренировке к IOI от KOTEHOK. Тогда её решил только PavelKunyavskiy и это был первый случай решения этой задачи на контесте (о котором знал ставивший нам тренировку). Этой осенью мы дали её на дистанционный тур кандидатам в сборную России, и там её решил только zemen, да и то не успел за время контеста написать полное решение — только на 60 баллов.
Теперь, собственно, решение (пока за "очень долго"). Насколько я понял, оно же в статье выше и описано.
Можно делать примерно то же самое, но добавлять по одному ребру, идеологически проще придумать и доказать, что будет работать
проверить можно тут: http://acm.mipt.ru/judge/problems.pl?problem=098
Can someone explain this in English, please?