Pagini recente » Cod sursa (job #2541656) | Cod sursa (job #2571618) | Cod sursa (job #754168) | Cod sursa (job #146445) | Cod sursa (job #303046)
Cod sursa(job #303046)
#include <stdio.h>
#define NM 100001
int st[NM];
int vf;
int n,m;
int ind[NM],low[NM],viz[NM];
int index;
int nr;
struct list{int nod;list *urm;} *rez[NM],*g[NM];
void df(int k);
inline void add(int x,int a)
{list *p=new list;
p->nod=a;
p->urm=g[x];
g[x]=p;
}
inline void addsol(int x,int a)
{list *p=new list;
p->nod=a;
p->urm=rez[x];
rez[x]=p;
}
int main()
{freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int i,x,y;
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++)
{scanf("%d %d",&x,&y);
add(x,y);
}
for (i=1;i<=n;i++)
if (!ind[i])
{df(i);
}
printf("%d\n",nr);
list *p;
for (i=1;i<=nr;i++)
{for (p=rez[i];p;p=p->urm)
{printf("%d ",p->nod);
}
printf("\n");
}
return 0;
}
void df(int k)
{index++;
ind[k]=index;
low[k]=index;
st[++vf]=k;
list *p;
for (p=g[k];p;p=p->urm)
if (!viz[p->nod])
{if (!ind[p->nod])
{df(p->nod);
}
if (low[p->nod]<low[k]) low[k]=low[p->nod];
}
if (low[k]==ind[k])
{nr++;
while (st[vf]!=k)
{viz[st[vf]]=1;
addsol(nr,st[vf]);
vf--;
}
addsol(nr,k);
viz[k]=1;
vf--;
}
}