По идее так:

1) Найдем компоненты сильной связности.

2) Возьмем какую-то одну компоненту и будем из какой-то ее вершины строить по 2 ребра в вершину каждой другой компоненты(одно ребро из компоненты, другое- в компоненту).

Благодаря этому из каждой компоненты можно будет добраться в каждую(через ту, что мы выбрали на шаге 2), а так как внутри компонент можно попасть в любую вершину, граф действительно станет связным.

Не, глупость сморозила. Не работает в общем случае.

Какая-то непростая задача, а откуда она?

А такой вариант может подойдет? 1) Найдем компоненты сильной связности 2) Сделаем цикл из этих компонент, т.е. по очереди из первой в N-ую компоненту проведем ребра. Возьмем в каждой компоненте любую вершину в которую будет входить ребро из i — 1 компоненты и выходить в i + 1 компоненту. Поправьте, если что не так)

Известная задача. Как-то хотел перевод сюда запилить, но руки не дошли

http://www.springer.com/cda/content/document/cda_downloaddocument/9780387235288-c2.pdf

Вроде бы ответ — это максимум из кол-ва компонент, в которые ничто не входит и из которых ничего не выходит. Ну и понятно, ка строить ответ тогда

Эта задачу я в первый раз увидел на тренировке к IOI от KOTEHOK. Тогда её решил только PavelKunyavskiy и это был первый случай решения этой задачи на контесте (о котором знал ставивший нам тренировку). Этой осенью мы дали её на дистанционный тур кандидатам в сборную России, и там её решил только zemen, да и то не успел за время контеста написать полное решение — только на 60 баллов.

Теперь, собственно, решение (пока за "очень долго"). Насколько я понял, оно же в статье выше и описано.

1. Сконденсировали граф.
2. Назовём истоками компоненты сильной связности, в которые не входят рёбря, стоками — из которых не выходят рёбра.
3. Предположили, что ответ — это максимум из количества стоков и истоков (за исключением случая, когда всё и так хорошо). Понятно, что бессмысленно проводить рёбра не из какого-нибудь стока в какой-нибудь исток (потому что если проверили, то давайте каждый из концов опустим/поднимем — станет не хуже).
4. Построим двудольный граф: одна доля из истоков, другая — из стоков, ребро из A в B, если есть путь из A в B в исходном графе.
5. Что можно делать с двудольным графом? Конечно же, искать максимальное паросочетание. Нашли.
6. Пусть нашлось A₁ → B₁, A₂ → B₂, .... Если это паросочетание полное, то у нас есть ответ: добавили рёбра B₁ → A₂, B₂ → A₃, ....
7. Теперь пусть неполное. Всё равно добавим рёбра, как в предыдущем пункте и сожмём получившуюся компоненту. Теперь граф имеет вид A₁ → X, A₂ → X, ..., X → B₁, X → B₂, .... В таком графе понятно как провести рёбра: провели жадно min(|A|, |B|) рёбер так, чтобы исходящая степень стока/входящая истока не превысила единицы, а затем оставшиеся — как-нибудь.
8. Вроде всё хорошо, но получился куб. Последнее замечание: мы пользовались несколько менее слабым фактом, чем то, что паросочетание максимально. Нам важно то, что нельзя провести никакой путь из истока в сток, не "задевающий" наши пути-рёбра из паросочетания в скондесированном графе. Если это так, то граф действительно принимает нужный вид после добавления рёбер.
9. А такое паросочетание найти просто, даже явно строить двудольный граф не надо — просто запустили dfs из всех истоков. Каждый dfs либо нашёл путь в сток (тогда запомнили их как ребро "паросочетания") или не нашёл. Метки снимать не надо. Итого линия.

проверить можно тут: http://acm.mipt.ru/judge/problems.pl?problem=098

Can someone explain this in English, please?