Pagini recente » Cod sursa (job #1420649) | Cod sursa (job #1642807) | Cod sursa (job #1478149) | Cod sursa (job #1074613) | Cod sursa (job #1166021)
#include<fstream>
#include<vector>
#include<stack>
#include<set>
using namespace std;
#define max_n 100010
ifstream f("ctc.in");
ofstream g("ctc.out");
int n , m , niv , ctc , x , y;
int Niv[max_n] , Low[max_n];
bool Viz[max_n];
vector< int > L[max_n];
set< int > Sol[max_n];
stack< int > S;
void read(){
f>>n>>m;
for( int i = 1 ; i <= m ; i++ ){
f>>x>>y;
L[x].push_back(y);
}
}
inline int minim( int a , int b ){
return a < b ? a : b;
}
void dfs( int nod ){
Niv[nod] = Low[nod] = (++niv);
S.push( nod ); Viz[nod] = 1;
for( unsigned int i = 0 ; i < L[nod].size() ; i++ ){
if( !Viz[ L[nod][i] ] )
dfs( L[nod][i] );
Low[nod] = minim( Low[nod] , Low[L[nod][i]] );
}
if( Niv[nod] == Low[nod] ){
ctc++;
while( S.top() != nod ){
Sol[ctc].insert( S.top() );
S.pop();
}
Sol[ctc].insert( S.top() );
S.pop();
}
}
void print(){
g<<ctc<<"\n";
for( int i = 1 ; i <= ctc ; i++ ){
for( set<int>::iterator it = Sol[i].begin() ; it != Sol[i].end() ; it++ )
g<<(*it)<<" ";
g<<"\n";
}
}
int main(){
read();
for( int i = 1 ; i <= n ; i++ )
if( !Viz[i] )
dfs(i);
print();
return 0;
}