Pagini recente » Cod sursa (job #173288) | Cod sursa (job #1720484) | Cod sursa (job #1650796)
#include <fstream>
#include <vector>
#define nmax 100005
#define pb push_back
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[nmax], GT[nmax], sol[nmax];
int viz[nmax], postordine[nmax], N, M, nr, nrCTC;
void citire()
{
int x, y;
fin>>N>>M;
for(int i=1; i<=M; i++)
{
fin>>x>>y;
G[x].pb(y);
GT[y].pb(x);
}
}
void DFS(int nod)
{
viz[nod] = 1;
for(int i=0; i<G[nod].size(); i++)
if(!viz[G[nod][i]])
DFS(G[nod][i]);
postordine[++nr] = nod;
}
void DFST(int nod)
{
viz[nod]=0; sol[nrCTC].pb(nod);
for(int i=0; i<GT[nod].size(); i++)
if(viz[GT[nod][i]])
DFST(GT[nod][i]);
}
int main()
{
citire();
int i, j;
for(i=1; i<=N; i++)
if(!viz[i]) DFS(i);
for(i=N; i>=0; i--)
if(viz[postordine[i]])
{
++nrCTC;
DFST(postordine[i]);
}
fout<<nrCTC<<'\n';
for(i=1; i<=nrCTC; i++)
{
for(j=0; j<sol[i].size(); j++)
fout<<sol[i][j]<<' ';
fout<<'\n';
}
return 0;
}