<ПРЕД Задача:
СЛЕД>
Задачу решил 51 пользователь: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Минимальное дополнение до сильно-связанного графа

Time limit = 5 секунд(ы)

Дан ориентированные граф. Добавьте минимальное количество ребер, чтобы сделать его сильно связанным.

Граф называется сильно связанным если для любых двух вершин A и B есть пути ведущие из A в B и обратно, из B в A.

Вход. Формат входных данных следующий:

V E
s1 t1
s2 t2
...
sE tE

V — число вершин (V < 10001). E — число рёбер (E < 100001). (si, ti) — описание i-го ребра. Вершины обозначаются числами 0, 1, ..., V-1.

Выход. В первой строчке выведите минимальное число рёбер M. Затем выведите M строчек с описанием этих рёбер.

Вход#1
4 3
0 1
1 2
1 3
Выход#1
2
3 0
2 0

Вход#2
6 5
0 2
1 2
2 3
3 4
4 5
Выход#2
2
5 0
5 1

Автор:

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 34.231.21.83