Pagini recente » Istoria paginii monthly-2012/runda-4/clasament | Cod sursa (job #2454449) | Cod sursa (job #657973) | Cod sursa (job #1940983) | Cod sursa (job #717829)
Cod sursa(job #717829)
#include<fstream>
#include<vector>
#include<stack>
#define pb push_back
#define INfile "biconex.in"
#define OUTfile "biconex.out"
#define NMAX 100009
using namespace std;
ifstream F ( INfile ) ;
ofstream G ( OUTfile ) ;
vector < int > V [ NMAX ] , SOL [ NMAX ] ;
stack < int > S ;
int N , M , cmp ;
int lvl [ NMAX ] , lwr [ NMAX ] ;
void solve () ;
void write () ;
void DFS ( int dad ) ;
void read () ;
int main ()
{
read () ;
solve () ;
write () ;
F.close () ;
G.close () ;
return 0 ;
}
void read ()
{
int i , x , y ;
F >> N >> M ;
for ( i = 1 ; i <= M ; ++ i )
{
F >> x >> y ;
V [ x ].pb ( y ) ;
V [ y ].pb ( x ) ;
}
}
void solve ()
{
int i ;
for ( i = 1 ; i <= N ; ++ i )
lwr [ i ] = 1 << 30 ;
for ( i = 1 ; i <= N ; ++ i )
if ( ! lvl [ i ] )
{
lvl [ i ] = 1 ;
S.push ( i ) ;
DFS ( i ) ;
}
}
void DFS ( int dad )
{
int i , son ;
for ( i = V [ dad ].size () - 1 ; i > -1 ; -- i )
{
son = V [ dad ][ i ] ;
if ( ! lvl [ son ] )
{
lvl [ son ] = lvl [ dad ] + 1 ;
S.push ( son ) ;
DFS ( son ) ;
if ( lwr [ son ] < lwr [ dad ] )
lwr [ dad ] = lwr [ son ] ;
if ( lwr [ son ] >= lvl [ dad ] )
{
++ cmp ;
while ( S.top () != dad )
{
SOL [ cmp ].pb ( S.top () ) ;
S.pop () ;
}
SOL [ cmp ].pb ( dad ) ;
}
}
else
if ( lvl [ son ] < lwr [ dad ] )
lwr [ dad ] = lvl [ son ] ;
}
}
void write ()
{
int i , j ;
G << cmp << '\n' ;
for ( i = 1 ; i <= cmp ; ++ i )
{
for ( j = SOL [ i ].size () - 1 ; j > -1 ; -- j )
G << SOL [ i ][ j ] << ' ' ;
G << '\n' ;
}
}