Pagini recente » Cod sursa (job #152838) | Cod sursa (job #1401948) | Cod sursa (job #315022) | Statisticile problemei Caramizi | Cod sursa (job #306565)
Cod sursa(job #306565)
#include<fstream.h>
struct nod
{int inf;
nod *adr;}*S,*G[100001];
int id[100001],l[100001],N,M,I,s[100001],a[200001],A,n;
void ad(nod *&l,short v)
{nod* p=new nod;p->inf=v;
p->adr=l;l=p;}
int st()
{int x=S->inf;
nod *p=S;S=S->adr;
delete p;return x;}
void tarjan(int v)
{id[v]=++I;l[v]=I;
ad(S,v);s[v]=1;
nod *p=G[v];
while(p)
{if(!id[p->inf]||s[p->inf])
{if(!id[p->inf])
tarjan(p->inf);
if(l[v]>l[p->inf])
l[v]=l[p->inf];}
p=p->adr;}
if(l[v]==id[v])
{++n;int x;
do
{x=st();s[x]=0;
a[++A]=x;}
while(x!=v);
a[++A]=0;}
}
int main()
{ifstream f("ctc.in");
ofstream g("ctc.out");
f>>N>>M;
int x,y;
for(;M;--M)
{f>>x>>y;
ad(G[x],y);}
for(x=1;x<=N;++x)
if(!id[x])
tarjan(x);
g<<n<<'\n';
for(x=1;x<A;++x)
if(a[x])
g<<a[x]<<' ';
else
g<<'\n';
return 0;
}