Pagini recente » Istoria paginii implica-te/arhiva-educationala | Cod sursa (job #3292064) | Cod sursa (job #235870)
Cod sursa(job #235870)
#include<stdio.h>
#define N 100010
struct nod{int inf;nod *urm;};
nod *v[N],*C[N];
int n,m,i,a,b,viz[N],stiva[N],low[N],dsfnum[N],top,num,nc;
void readd(),solve(),visit(int p),prints();
int main()
{
readd();
solve();
prints();
return 0;
}
void readd()
{ nod *paux;
freopen("ctc.in","rt",stdin);
freopen("ctc.out","wt",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{ scanf("%d%d",&a,&b);
paux=new nod;
paux->inf=b;
paux->urm=v[a];
v[a]=paux;
}
}
void solve()
{ for(i=1;i<=n;i++)
if(!viz[i]){num=0;visit(i);}
}
void visit(int p)
{ nod *paux;
viz[p]=1;
stiva[++top]=p;//add p to L
dsfnum[p]=++num;//increment N
low[p]=dsfnum[p];
for(paux=v[p];paux;paux=paux->urm)
{ if(viz[paux->inf]==2)continue;
if(!viz[paux->inf]) visit(paux->inf);
low[p]=(low[p]<low[paux->inf])?low[p]:low[paux->inf];
}
if(low[p]==dsfnum[p])
{ nc++;
for(;;)
{
paux=new nod;
paux->inf=stiva[top];
viz[stiva[top]]=2;
paux->urm=C[nc];
C[nc]=paux;
top--;
if(stiva[top+1]==p)break;
}
}
}
void prints()
{ nod *paux;
printf("%d",nc);
for(i=1;i<=nc;i++)
{ printf("\n");
for(paux=C[i];paux;paux=paux->urm)
printf("%d ",paux->inf);
}
printf("\n");
}