Pagini recente » Cod sursa (job #1074055) | Cod sursa (job #871732) | Cod sursa (job #1604962) | Cod sursa (job #605554) | Cod sursa (job #704410)
Cod sursa(job #704410)
#include <cstdio>
#define nd 100005
using namespace std;
struct nod{int val; nod *urm;}*g[nd],*gt[nd],*ctc[nd];
int m,n,sol;
int st[nd];
bool viz[nd];
void read()
{ int i,x,y;
nod *aux;
freopen("ctc.in","r",stdin); scanf("%d %d\n",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%d %d\n",&x,&y);
aux=new nod; aux->val=y; aux->urm=g[x]; g[x]=aux;
aux=new nod; aux->val=x; aux->urm=gt[y]; gt[y]=aux;
}
fclose(stdin);
}
void write()
{ int i;
nod *aux;
freopen("ctc.out","w",stdout); printf("%d\n",sol);
for(i=1;i<=sol;++i)
{
for(aux=ctc[i];aux!=NULL;aux=aux->urm)
printf("%d ",aux->val);
printf("\n");
}
fclose(stdout);
}
void df(int ind)
{ nod *aux;
viz[ind]=1;
for(aux=g[ind];aux!=NULL;aux=aux->urm)
if(viz[aux->val]==0)df(aux->val);
st[++st[0]]=ind;
}
void df2(int ind)
{ nod *aux;
viz[ind]=0;
aux=new nod; aux->val=ind; aux->urm=ctc[sol]; ctc[sol]=aux;
for(aux=gt[ind];aux!=NULL;aux=aux->urm)
if(viz[aux->val]==1)df2(aux->val);
}
int main()
{ int i;
read();
for(i=1;i<=n;++i)
if(viz[i]==0)df(i);
sol=0;
for(i=n;i>=1;--i)
if(viz[st[i]]==1){ ++sol; df2(st[i]); }
write();
return 0;
}