Pagini recente » Cod sursa (job #825607) | Cod sursa (job #2118442) | Cod sursa (job #1019837) | Cod sursa (job #38960) | Cod sursa (job #2314333)
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
const int NMAX = 100005;
int N, M;
vector <int> Ad[NMAX];
vector <int> Ad_rev[NMAX];
vector <int> T;
bool vis[NMAX];
void Read()
{
fin >> N >> M;
int x, y;
for( int i = 1; i <= M; ++i )
{
fin >> x >> y;
Ad[x].push_back(y);
}
fin.close();
}
void Topo( int nod )
{
vis[nod] = true;
int w;
for( int i = 0; i < Ad[nod].size(); ++i )
{
w = Ad[nod][i];
if( !vis[w] ) Topo( w );
}
T.push_back( nod );
}
void DFS( int nod, bool printt )
{
vis[nod] = true;
if( printt ) fout << nod << ' ';
int w;
for( int i = 0; i < Ad_rev[nod].size(); ++i )
{
w = Ad_rev[nod][i];
if( !vis[w] ) DFS( w, printt );
}
}
void Do()
{
for( int i = 1; i <= N; ++i )
if( !vis[i] )
Topo( i );
int w;
for( int i = 1; i <= N; ++i )
{
for( int j = 0; j < Ad[i].size(); ++j )
{
w = Ad[i][j];
Ad_rev[w].push_back(i);
}
}
int nr_comp = 0;
for( int i = 0; i <= N; ++i )
vis[i] = 0;
for( int i = T.size() - 1; i >= 0; --i )
if( vis[T[i]] == false )
{
++nr_comp;
DFS( T[i], false );
}
fout << nr_comp << '\n';
for( int i = 0; i <= N; ++i )
vis[i] = 0;
for( int i = T.size() - 1; i >= 0; --i )
if( vis[T[i]] == false )
{
++nr_comp;
DFS( T[i], true );
fout << '\n';
}
fout.close();
}
int main()
{
Read();
Do();
return 0;
}