Pagini recente » Cod sursa (job #800033) | Monitorul de evaluare | Cod sursa (job #2389389) | Borderou de evaluare (job #3118045) | Cod sursa (job #1386437)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define Nmax 100002
#define pb push_back
FILE *f = fopen ( "ctc.in", "r" );
FILE *g = fopen ( "ctc.out", "w" );
vector < int > G[Nmax], sol[Nmax];
stack < int > st;
int idx[Nmax], lowlink[Nmax], index = 1, nrsol;
bool inStack[Nmax];
void Tarjan ( int nod ){
vector < int > :: iterator it;
idx[nod] = index;
lowlink[nod] = index;
index++;
st.push ( nod );
inStack[nod] = 1;
for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
if ( !idx[*it] ){
Tarjan ( *it );
lowlink[nod] = min ( lowlink[nod], lowlink[*it] );
}
else{
if ( inStack[*it] ){
lowlink[nod] = min ( lowlink[nod], lowlink[*it] );
}
}
}
if ( lowlink[nod] == idx[nod] ){
nrsol++;
int k;
do{
k = st.top();
sol[nrsol].pb ( k );
st.pop();
inStack[k] = 0;
}while ( k != nod );
}
}
int main(){
int N, M, x, y;
vector < int > :: iterator it;
fscanf ( f, "%d%d", &N, &M );
for ( int i = 1; i <= M; ++i ){
fscanf ( f, "%d%d", &x, &y );
G[x].pb ( y );
}
for ( int i = 1; i <= N; ++i )
if ( !idx[i] )
Tarjan ( i );
fprintf ( g, "%d\n", nrsol );
for ( int i = 1; i <= nrsol; ++i ){
for ( it = sol[i].begin(); it < sol[i].end(); ++it )
fprintf ( g, "%d ", *it );
fprintf ( g, "\n" );
}
return 0;
}