Pagini recente » Cod sursa (job #1061089) | Cod sursa (job #1389059) | Cod sursa (job #232769) | Cod sursa (job #1768449) | Cod sursa (job #2080582)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define pb push_back
int N, M, nr;
vector <int> G[100001], GT[100001], PostOrdine, CTC[100001];
vector <bool> Viz;
void DFS(int x)
{
int i;
Viz[x] = true;
for(i = 0; i < G[x].size(); ++i)
if(!Viz[G[x][i]]) DFS(G[x][i]);
PostOrdine.pb(x);
}
void DFST(int x)
{
int i;
Viz[x] = false;
CTC[nr].pb(x);
for(i = 0; i < GT[x].size(); ++i)
if(Viz[GT[x][i]] == true) DFST(GT[x][i]);
}
int main()
{
int i, j, k;
fin>>N>>M;
for(k = 1; k <= M; ++k)
{
fin>>i>>j;
G[i].pb(j);
GT[j].pb(i);
}
Viz.assign(N + 1, false);
for(i = 1; i <= N; ++i)
if(!Viz[i]) DFS(i);
for(i = N - 1; i >= 0; --i)
if(Viz[PostOrdine[i]] == true)
{
nr++;
DFST(PostOrdine[i]);
}
fout<<nr<<'\n';
for(i = 1; i <= nr; ++i)
{
for(j = 0; j < CTC[i].size(); ++j)
fout<<CTC[i][j]<<' ';
fout<<'\n';
}
return 0;
}