Pagini recente » Istoria paginii clasament-arhiva | Diferente pentru implica-te/arhiva-educationala intre reviziile 199 si 223 | Atasamentele paginii implica-te/arhiva-educationala/membri-emeritus | Diferente pentru implica-te/arhiva-educationala intre reviziile 174 si 223 | Cod sursa (job #235864)
Cod sursa(job #235864)
#include<stdio.h>
#define N 100001
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])
{
visit(paux->inf);
low[p]=(low[p]<low[paux->inf])?low[p]:low[paux->inf];
}
else
low[p]=(low[p]<dsfnum[paux->inf])?low[p]:dsfnum[paux->inf];
}
if(low[p]==dsfnum[p])
{ nc++;
for(;;)
{
paux=new nod;
paux->inf=stiva[top];
paux->urm=C[nc];
C[nc]=paux;
top--;
if(stiva[top+1]==p)break;
}
if(!(C[nc]->urm)){C[nc]=0;nc--;}
}
}
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");
}