Pagini recente » Cod sursa (job #992355) | Cod sursa (job #2901562) | Cod sursa (job #3180899) | Cod sursa (job #2538466) | Cod sursa (job #1090226)
#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
#define MAXN 100010
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int>G[MAXN];
vector<int>Gt[MAXN];
vector<int>now;
vector<vector<int>>Sol;
bool Viz[MAXN];
int St[MAXN];
void TopSort( int nod){
Viz[nod] = 1;
for ( auto it : Gt[nod])
if ( !Viz[it])
TopSort(it);
St[++St[0]] = nod;
}
void DFS(int nod)
{
now.push_back(nod);
Viz[nod]=1;
for ( auto it : G[nod] )
if ( !Viz[it])
DFS(it);
}
int main()
{
int N,M;
in >> N >> M;
int i,x,y;
for ( i = 1 ; i <= M ; i ++)
{
in >> x >> y;
G[x].push_back(y);
Gt[y].push_back(x);
}
for ( i = 1 ; i <= N ; i ++)
if ( !Viz[i])
TopSort (i);
memset(Viz,0,sizeof(Viz));
for ( i = N ; i >= 1 ; i --)
if ( !Viz[St[i]] )
{
DFS (St[i]);
Sol.push_back(now);
now.clear();
}
int Sz = Sol.size();
out << Sz << "\n";
for ( i = 0 ; i < Sz ; i ++)
{
for ( auto it : Sol[i])
out << it << " ";
out << "\n";
}
return 0;
}