Cod sursa(job #306565)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 21 aprilie 2009 13:29:19
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#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;
}