Pagini recente » Cod sursa (job #1156038) | Cod sursa (job #1949440) | Cod sursa (job #2469342) | Cod sursa (job #2841783) | Cod sursa (job #1250458)
//#include <fstream>
#include <cstdio>
#include <vector>
#define DMAX 100005
using namespace std;
FILE*fin=fopen("ctc.in","r");
FILE*fout=fopen("ctc.out","w");
void citire();
void rezolvare();
void DFSG(int vf);
void DFST(int vf);
void clear();
void afisare();
vector <int> G[DMAX];
vector <int> T[DMAX];
vector <int> sol[DMAX];
int n,m,nrctc,pozpo;
int uz[DMAX];
int postord[DMAX];
int main()
{
citire();
rezolvare();
afisare();
return 0;
}
void citire()
{
int i,x,y;
fscanf(fin,"%d %d",&n,&m);
for (i=1;i<=m;i++)
{
fscanf(fin,"%d %d",&x,&y);
G[x].push_back(y);
T[y].push_back(x);
}
}
void rezolvare()
{
int i;
for (i=1;i<=n;i++)
if (uz[i]==0) DFSG(i);
clear();
for (i=n;i>=1;i--)
if(uz[postord[i]]==0)
{
nrctc++;
DFST(postord[i]);
}
}
void clear()
{
int i;
for (i=1;i<=n;i++) uz[i]=0;
}
void DFSG(int vf)
{
int i;
uz[vf]=1;
for (i=0;i<G[vf].size();i++)
if (uz[ G[vf][i] ]==0) DFSG(G[vf][i]);
postord[++pozpo]=vf;
}
void DFST(int vf)
{
int i;
sol[nrctc].push_back(vf);
uz[vf]=1;
for (i=0;i<T[vf].size();i++)
if ( uz[ T[vf][i] ]==0) DFST(T[vf][i]);
}
void afisare()
{
int i,j;
fprintf(fout,"%d\n",nrctc);
for (i=1;i<=nrctc;i++)
{for (j=0;j<sol[i].size();j++)
fprintf(fout,"%d ",sol[i][j]);
fprintf(fout,"\n");
}
}