Pagini recente » Cod sursa (job #439091) | Cod sursa (job #1345726) | Cod sursa (job #2463770) | Cod sursa (job #1912792) | Cod sursa (job #3280660)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out");
#define cin fin
#define cout fout
#define PB push_back
const int Nmax = 1e5;
vector<int> out[Nmax + 1], in[Nmax + 1];
vector< vector<int> > comp;
bool processed[Nmax+1];
vector<int> l;
inline void dfs ( int nod ) {
int i, nod2;
if ( !processed[nod] ) {
processed[nod] = true;
for ( i = 0; i < out[nod].size(); i ++ ) {
nod2 = out[nod][i];
if ( !processed[nod2] )
dfs( nod2 );
}
l.PB( nod );
}
}
inline void dfs2 ( int nod ) {
int i, nod2;
if ( !processed[nod] )
comp.PB( {nod} );
processed[nod] = true;
for ( i = 0; i < in[nod].size(); i ++ ) {
nod2 = in[nod][i];
if ( !processed[nod2] ) {
processed[nod2] = true;
comp[comp.size()-1].PB( nod2 );
dfs2( nod2 );
}
}
}
int main()
{
int n, m, nod1, nod2, i, j;
cin >> n >> m;
for ( i = 0; i < m; i ++ ) {
cin >> nod1 >> nod2;
out[nod1].PB( nod2 );
in[nod2].PB( nod1 );
}
for ( i = 1; i<=n; i ++ )
dfs( i );
for ( i = 1; i <=n; i ++ )
processed[i] = false;
for ( i = n - 1; i >= 0; i -- ) {
dfs2( l[i] );
}
cout << comp.size() << "\n";
for ( i = 0; i < comp.size(); i ++ ) {
for ( j = 0; j < comp[i].size(); j ++ )
cout << comp[i][j] << " ";
cout << "\n";
}
return 0;
}