Pagini recente » Cod sursa (job #1446398) | Cod sursa (job #1021072) | Cod sursa (job #1206900) | Cod sursa (job #994734) | Cod sursa (job #1441138)
#include <fstream>
#include <vector>
using namespace std;
ifstream f ( "ctc.in" );
ofstream g ( "ctc.out" );
vector<int> G[100001], H[100001];
int viz[100001];
int n, m, po[100001], nr;
int comp;
vector <int> v[100001];
void dfs ( int x )
{
viz[x] = 1;
for ( int i = 0; i < G[x].size(); i++ )
if ( !viz[G[x][i]] )
dfs ( G[x][i] );
po[nr++] = x;
}
void dfst ( int x )
{
viz[x] = 0;
for ( int i = 0; i < H[x].size(); i++ )
if ( viz[H[x][i]] )
dfst ( H[x][i] );
v[comp].push_back ( x );
}
int main()
{
int i, a, b;
f >> n >> m;
for ( i = 1; i <= m; i++ )
{
f >> a >> b;
G[a].push_back ( b );
H[b].push_back ( a );
}
for ( i = 1; i <= n; i++ )
if ( !viz[i] )
dfs ( i );
for ( i = n; i >= 1; i-- )
if ( viz[po[i]] )
{
comp++;
dfst ( po[i] );
}
g << comp << "\n";
for ( i = 1; i <= comp; i++ )
{
for ( int j = v[i].size() - 1; j >= 0; j-- )
g << v[i][j] << " ";
g << "\n";
}
f.close();
g.close();
return 0;
}