Pagini recente » Cod sursa (job #916102) | Cod sursa (job #728585) | Cod sursa (job #2515775) | Cod sursa (job #2470304) | Cod sursa (job #981499)
Cod sursa(job #981499)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define Nmax 100002
vector<int> S[Nmax];
vector<int> G[Nmax];
vector<int> GT[Nmax];
vector<int> postordine(Nmax);
vector<bool> viz(Nmax);
int N, M, P, nr;
void read()
{
ifstream f("ctc.in");
f >> N >> M;
for ( int i = 1, a, b; i <= M; ++i )
{
f >> a >> b;
G[a].push_back( b );
GT[b].push_back( a );
}
f.close();
}
void DFS( int node )
{
viz[node] = 1;
for ( unsigned i = 0; i < G[node].size(); ++i )
{
if ( !viz[ G[node][i] ] )
{
DFS( G[node][i] );
}
}
postordine[ ++P ] = node;
}
void DFST( int node )
{
viz[node] = 0;
S[nr].push_back( node );
for ( unsigned i = 0; i < GT[node].size(); ++i )
{
if ( viz[ GT[node][i] ] )
{
DFST( GT[node][i] );
}
}
}
void solve()
{
for ( int i = 1; i <= N; ++i )
if ( !viz[i] )
DFS( i );
for ( int i = N; i >= 1; i-- )
{
if ( viz[ postordine[i] ] )
{
nr++;
DFST( postordine[i] );
}
}
}
void print()
{
ofstream g("ctc.out");
g << nr << "\n";
for ( int i = 1; i <= nr; ++i )
{
for ( unsigned j = 0; j < S[i].size(); ++j )
g << S[i][j] << " ";
g << "\n";
}
g.close();
}
int main()
{
read();
solve();
print();
return 0;
}