Pagini recente » Cod sursa (job #1327046) | Cod sursa (job #265435) | Cod sursa (job #2329447) | Cod sursa (job #1096308) | Cod sursa (job #390651)
Cod sursa(job #390651)
#include <stdio.h>
struct node
{
int nr;
node *adr;
};
int n,m,i,a,b,s[100005],nrc,min[100005],st[100005],ns,sol;
node *v[100005],*u,*comp[100005];
void tarjan(int nod)
{
node *u;
int d;
s[nod]=1;
st[++ns]=nod;
d=++nrc;
min[nod]=nrc;
for (u=v[nod];u!=NULL;u=u->adr)
{
if (!s[u->nr])
{
tarjan(u->nr);
if (min[u->nr]<min[nod])
min[nod]=min[u->nr];
}
else
if (s[u->nr]==1 && min[u->nr]<min[nod])
min[nod]=min[u->nr];
}
if (min[nod]==d)
{
++sol;
while (st[ns]!=nod)
{
u=new node;
u->nr=st[ns];
u->adr=comp[sol];
comp[sol]=u;
s[st[ns]]=2;
--ns;
}
u=new node;
u->nr=nod;
u->adr=comp[sol];
comp[sol]=u;
s[nod]=2;
--ns;
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;++i)
{
scanf("%d %d",&a,&b);
u=new node;
u->nr=b;
u->adr=v[a];
v[a]=u;
}
for (i=1;i<=n;++i)
if (!s[i])
tarjan(i);
printf("%d\n",sol);
for (i=1;i<=sol;++i)
{
for (u=comp[i];u!=NULL;u=u->adr)
printf("%d ",u->nr);
printf("\n");
}
return 0;
}