Pagini recente » Cod sursa (job #2154587) | Cod sursa (job #2485188) | Cod sursa (job #2590249) | Cod sursa (job #2324159) | Cod sursa (job #1027201)
#include<fstream>
#include<vector>
using namespace std;
#define max_n 100010
ifstream f("ctc.in");
ofstream g("ctc.out");
int n , m , x , y , k , nr , niv1;
vector<int>L[max_n] , Ctc[max_n];
int stack[max_n] , niv[max_n] , low[max_n];
bool Fr[max_n];
void read(){
f>>n>>m;
for( int i = 1 ; i <= m ; i++ ){
f>>x>>y;
L[x].push_back(y);
}
}
void dfs( int nod ){
stack[++k] = nod;
niv[nod] = ++niv1; low[nod] = niv1;
for( unsigned int i = 0 ; i < L[nod].size() ; i++ ){
if( niv[L[nod][i]] == 0 )
dfs( L[nod][i] );
if( low[L[nod][i]] < low[nod] && Fr[L[nod][i]] == 0 )
low[nod] = low[L[nod][i]];
}
if( niv[nod] == low[nod] ){
nr++;
do{
x = stack[k--];
Ctc[nr].push_back(x);
Fr[x] = 1;
}while( x != nod );
}
}
int main(){
read();
for( int i = 1 ; i <= n ; i++ )
if( niv[i] == 0 )
dfs(i);
g<<nr<<"\n";
for( int i = 1 ; i <= nr ; i++ ){
for( int j = 0 ; j < Ctc[i].size() ; j++ )
g<<Ctc[i][j]<<" ";
g<<"\n";
}
return 0;
}