Pagini recente » Cod sursa (job #10482) | Cod sursa (job #1520182) | Cod sursa (job #2802544) | Cod sursa (job #2856929) | Cod sursa (job #2309745)
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
const int NR = 100001 ;
ifstream f ("ctc.in") ;
ofstream g ("ctc.out") ;
vector < int > v [ NR ] ;
vector < int > d ( NR , -1 ) ;
vector < int > st ;
vector < bool > viz ( NR , false ) ;
vector < int > ctc [ NR ] ;
int nrctc ;
int dfs ( int nod , int deph )
{
viz [ nod ] = true ;
st.pb( nod ) ;
d [ nod ] = deph ;
for ( size_t i = 0 ; i < v [ nod ].size() ; ++ i )
{
int vecin = v [ nod ][ i ] ;
if ( d [ vecin ] == -1 ) d [ nod ] = min ( d [ nod ] , dfs ( vecin , deph + 1 ) ) ;
else
{
if ( viz [ vecin ] ) d [ nod ] = min ( d [ nod ] , d [ vecin ] ) ;
}
}
int nodulet ;
if ( deph == d [ nod ] )
{
nrctc ++ ;
do
{
nodulet = st.back() ;
st.pop_back() ;
ctc[ nrctc] .pb ( nodulet ) ;
viz [ nodulet ] = false ;
}
while ( nodulet != nod ) ;
}
return d [ nod ] ;
}
int main()
{
int n , m , i ; f >> n >> m ;
while ( m -- ) { int a , b ; f >> a >> b ; v [ a ].pb(b) ; }
dfs ( 1 , 1 ) ;
g << nrctc << "\n" ;
for ( i = 1 ; i <= nrctc ; ++ i , g << "\n" )
for ( size_t j = 0 ; j < ctc [ i ].size() ; ++ j ) g << ctc [ i ][ j ] << " " ;
f.close() ;
g.close() ;
return 0 ;
}