<PREV Problem:
NEXT>
Solved by 51 users: ...
UserDateAttemptTimeCMSC
Krot23 oct 2011C++500.29727 
gawry25 jul 2006C++301.08728 
Ekaterina_10 may 2014C++200.66732 
akopich27 jan 2010C++100.79740 
Ekaterina_10 may 2014C++100.65748 
igor.a.ehrlich14 sep 2011C++100.26753 
dzhavaharnal24 aug 2016C++100.26753 
tulindanil30 may 2015C++100.28753 
Krot22 oct 2011C++100.29753 
tron20 dec 2012C++100.29753 
danicheeeeeeeeee20 nov 2016C++200.30753 
mtretyak20 may 2015C++100.30755 
Languages
C++
46
FPC
4
Java
1
Kylix
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Upgrading to strongly connected graph

Time limit = 5 second(s)

You are given directed graph. Add minimal number of edges to make it strongly connected.

Graph is strongly connected iff for any vertices A and B there are paths from A to B, and from B to A.

Input. Input format is

V E
s1 t1
s2 t2
...

sE tE

Here V is number of vertices (V < 10001), E is number of edges (E < 100001), (si, ti) is i-th edge description. Vertices are denoted by numbers 0, 1, ..., V-1.

Output. The first line should contain the minimal number M of edges to add. Then M lines with their description should follow.

Input#1
4 3
0 1
1 2
1 3
Output#1
2
3 0
2 0

Input#2
6 5
0 2
1 2
2 3
3 4
4 5
Output#2
2
5 0
5 1

Author:
Well-known problem. Tests and description by Artem Voroztsov. Checker by Dmitry Korolev.
10 May 2006

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 3.228.220.31