Pagini recente » Cod sursa (job #252101) | Cod sursa (job #1572701) | Cod sursa (job #1348578) | Cod sursa (job #2670393) | Cod sursa (job #2680594)
#include <fstream>
#include <vector>
#include <stack>
#define f in
#define g out
using namespace std;
ifstream in ( "ctc.in" );
ofstream out( "ctc.out" );
int n, m, i, x, y, nivel, ctc;
int niv[100100], low[100100], fr[100100];
vector<int> L[100100], sol[100100];
stack<int> s;
void dfs( int nod ){
nivel++;
niv[nod] = nivel;
low[nod] = nivel;
s.push(nod);
fr[nod] = 1;
for ( auto vecin: L[nod] )
if ( !niv[vecin] ){
dfs(vecin);
low[nod] = min ( low[nod], low[vecin] );
} else if ( fr[vecin] )
low[nod] = min ( low[nod], low[vecin] );
if ( niv[nod] == low[nod] ){
ctc++;
x = nod;
do {
x = s.top();
sol[ctc].push_back(x);
fr[x] = 0;
s.pop();
} while ( x != nod );
}
}
int main() {
f>>n>>m;
for ( i=1; i <= m; i++ ){
f>>x>>y;
L[x].push_back(y);
}
for ( i=1; i <= n; i++ )
if ( !niv[i] )
dfs(i);
g<<ctc<<"\n";
for ( i=1; i <= ctc; i++, g<<"\n" )
for ( auto nod: sol[i] )
g<<nod<<" ";
return 0;
}