Pagini recente » Cod sursa (job #1651241) | Cod sursa (job #873284) | Cod sursa (job #1504121) | Cod sursa (job #2899480) | Cod sursa (job #2314916)
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
vector <int> G[N], Gt[N];
int n, m, ct;
stack <int> S;
bool viz[N], vizt[N];
vector <int> comp[N];
void read()
{
int i, x, y;
fin >> n >> m;
for ( i = 1; i <= m; ++i )
{ fin >> x >> y;
G[x].push_back(y);
Gt[y].push_back(x);
}
fin.close();
}
void topo( int x )
{
viz[x] = 1;
int i;
for ( i = 0; i < G[x].size(); ++i )
if ( !viz[G[x][i]] )
topo(G[x][i]);
S.push(x);
}
void DFS( int x )
{
comp[ct].push_back(x);
int i;
vizt[x] = 1;
for ( i = 0; i < Gt[x].size(); ++i )
if ( !vizt[Gt[x][i]] )
DFS(Gt[x][i]);
}
void solve()
{
int i, j, x;
for ( i = 1; i <= n; ++i )
if ( !viz[i] )
topo(i);
while ( !S.empty() )
{ x = S.top();
S.pop();
if ( !vizt[x] )
{ ct++;
DFS(x);
}
}
fout << ct << '\n';
for ( i = 1; i <= ct; ++i )
{ sort( comp[i].begin(), comp[i].end() );
for ( j = 0; j < comp[i].size(); ++j )
fout << comp[i][j] << ' ';
fout << '\n';
}
}
int main()
{ read();
solve();
return 0;
}