Pagini recente » Cod sursa (job #1698120) | Cod sursa (job #1794883) | Cod sursa (job #2342024) | Cod sursa (job #2602608) | Cod sursa (job #1038353)
#include <cstdio>
#include <vector>
#define NMAX 100010
using namespace std;
FILE *fin,*fout;
vector <int> M[NMAX],MT[NMAX],v[NMAX];
int use[NMAX],postordine[NMAX],adaugat[NMAX];
int n,m,cat,z,CAT;
void DFS(int);
void DFST(int);
int main()
{
fin=fopen("ctc.in","r");
fout=fopen("ctc.out","w");
int i,k,x,j,dim;
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&k,&x);
M[k].push_back(x);
MT[x].push_back(k);
}
for(i=1;i<=n;i++)
if(use[i]==0)
{
DFS(i);
}
for(i=n;i>=1;i--)
use[i]=0;
for(i=cat;i>=1;i--)
if(use[postordine[i]]==0)
{
CAT++;
DFST(postordine[i]);
}
fprintf(fout,"%d\n",CAT);
for(i=1;i<=CAT;i++)
{
dim=v[i].size();
for(j=0;j<dim;j++)
fprintf(fout,"%d ",v[i][j]);
fprintf(fout,"\n");
}
return 0;
}
void DFST(int x)
{
int i=0,dim;
use[x]=1;
dim=MT[x].size();
for(i=0;i<dim;i++)
{ if(use[MT[x][i]]==0)
{
DFST(MT[x][i]);
}
}
v[CAT].push_back(x);
}
void DFS(int x)
{
int i,dim;
dim=M[x].size();
for(i=0;i<dim;i++)
{
if(use[M[x][i]]==0)
{
use[M[x][i]]=1;
DFS(M[x][i]);
}
}
cat++;
postordine[cat]=x;
}