Pagini recente » Cod sursa (job #2925826) | Cod sursa (job #864370) | Cod sursa (job #909200) | Cod sursa (job #2127819) | Cod sursa (job #347180)
Cod sursa(job #347180)
#include <stdio.h>
#define DIM 100005
struct Nod{
int x;
Nod *adr;};
Nod *graf[DIM], *graft[DIM], *sol[DIM];
int n, m, viz[DIM], postviz[DIM], l, nr;
void add(Nod *&p, int s)
{
Nod *q;
q=new Nod;
q->adr=p;
q->x=s;
p=q;
}
void df(int k)
{
Nod *p;
viz[k]=1;
for (p=graf[k]; p; p=p->adr)
if (!viz[p->x])
df(p->x);
postviz[++l]=k;
}
void dft(int k)
{
Nod *p;
viz[k]=0;
add(sol[nr], k);
for (p=graft[k]; p; p=p->adr)
if (viz[p->x])
dft(p->x);
}
void afisare ()
{
Nod *p;
int i;
printf ("%d\n",nr);
for (i=1; i<=nr; ++i)
{
for (p=sol[i]; p; p=p->adr)
printf ("%d ",p->x);
printf ("\n");
}
}
int main()
{
int x, y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1; i<=m; ++i)
{
scanf("%d%d",&x,&y);
add(graf[x],y);
add(graft[y],x);
}
for (int i=1; i<=n; ++i)
if (!viz[i])
df(i);
for (int i=n; i; --i)
if (viz[postviz[i]])
{
++nr;
dft(postviz[i]);
}
afisare();
return 0;
}