Pagini recente » Cod sursa (job #204621) | Cod sursa (job #487808) | Cod sursa (job #1636666) | Cod sursa (job #2655982) | Cod sursa (job #581746)
Cod sursa(job #581746)
#include <stdio.h>
int n,m,i,x,y,st[100011],nrc,luat[100011],idx[100011],low[100011],indecs;
struct nod{int y; nod *next;};
nod *G[100011],*C[100011];
int add(int a, int b)
{
nod *nou=new nod;
nou->y=b;
nou->next=G[a];
G[a]=nou;
return 0;
}
int gaseste(int vf)
{
idx[vf]=low[vf]=indecs;
indecs++;
st[++st[0]]=vf;
luat[vf]=1;
nod *it=new nod;
it=G[vf];
while (it)
{
if (idx[it->y]==-1) {gaseste(it->y); if (low[vf]>low[it->y]) low[vf]=low[it->y];}
else if (luat[it->y]) if (low[vf]>low[it->y]) low[vf]=low[it->y];
it=it->next;
}
if (idx[vf]==low[vf])
{
nrc++;
do
{
nod *nou=new nod;
nou->y=st[st[0]];
luat[st[st[0]]]=0;
st[0]--;
nou->next=C[nrc];
C[nrc]=nou;
}while (st[st[0]+1]!=vf);
}
}
int main(void)
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
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++)
{
idx[i]=-1;
luat[i]=0;
}
for (i=1;i<=n;i++)
if (idx[i]==-1) gaseste(i);
printf("%d\n",nrc);
for (i=1;i<=nrc;i++)
{
nod *it=new nod;
it=C[i];
while (it)
{
printf("%d ",it->y);
it=it->next;
}
printf("\n");
}
return 0;
}