Pagini recente » Cod sursa (job #1948647) | Cod sursa (job #866911) | Cod sursa (job #2555375) | Cod sursa (job #2543371) | Cod sursa (job #349431)
Cod sursa(job #349431)
#include <cstdio>
#include <string>
#define MaxN 100009
struct muchie{
int x;
muchie *urm;
};
muchie *suc[MaxN],*pred[MaxN],*sol[MaxN],*aux;
int n,m,c[MaxN],uz[MaxN],nr,i,x,y,N;
//int *suc[MaxN],*pred[MaxN],*sol[MaxN];
void add_suc(int x,int y)
{
muchie *aux=new muchie;
aux->x=y; aux->urm=suc[x]; suc[x]=aux;
}
void add_pred(int x,int y)
{
muchie *aux=new muchie;
aux->x=x; aux->urm=pred[y]; pred[y]=aux;
}
void dfs(int nod)
{
muchie *aux=new muchie;
uz[nod]=1;
aux=suc[nod];
while(aux)
{
if(!uz[aux->x])
dfs(aux->x);
aux=aux->urm;
}
c[++N]=nod;
}
void df(int nod,int nr)
{
uz[nod]=1;
muchie *aux=new muchie;
aux->x=nod; aux->urm=sol[nr];
sol[nr]=aux;
aux=pred[nod];
while(aux)
{
if(!uz[aux->x])
df(aux->x,nr);
aux=aux->urm;
}
}
int main()
{
freopen("ctc.in","r",stdin);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add_suc(x,y);
add_pred(x,y);
}
for(i=1;i<=n;i++)
if(!uz[i])
dfs(i);
memset(uz,0,sizeof(uz));
for(i=N;i>=1;i--)
if(!uz[c[i]])
nr++, df(c[i],nr);
freopen("ctc.out","w",stdout);
printf("%d\n",nr);
for(i=1;i<=nr;i++)
{
aux=sol[i];
while(aux)
{
printf("%d ",aux->x);
aux=aux->urm;
}
printf("\n");
}
return 0;
}