Pagini recente » Cod sursa (job #1839288) | Cod sursa (job #2470035) | Cod sursa (job #1561008) | Cod sursa (job #1034333) | Cod sursa (job #588631)
Cod sursa(job #588631)
#include<fstream.h>
#define N 100001
long n,m,deg[N]={0},*g[N],k,i,j,t=0,ind,c[N],l[N],nr,a[2*N],b[2*N],u,p,r,v[N]={0},s[2*N],q[2*N],ss,sq;
void tarjan(long i,long *nr,long *ind)
{long j,r,k;
s[++ss]=i;
if(v[i]==0)
v[i]=1;
c[i]=(*ind);
l[i]=(*ind)++;
for(j=0;j<deg[i];j++)
if(c[g[i][j]]==0)
{tarjan(g[i][j],nr,ind);
if(l[i]>l[g[i][j]])
l[i]=l[g[i][j]];}
else
if(v[g[i][j]]==1&&l[i]>c[g[i][j]])
l[i]=c[g[i][j]];
if(c[i]==l[i])
{(*nr)++;
k=0;
while(ss)
{r=s[ss--];
if(r!=i&&v[r]==1)
q[++sq]=r,k++,v[r]=2;
else
break;}
if(v[i]==1)
v[i]=2,k++,q[++sq]=i;
if(k==0)
(*nr)--;
else
q[++sq]=0;}}
int main()
{ifstream x("ctc.in");
ofstream y("ctc.out");
x>>n>>m;
for(k=1;k<=m;k++)
{x>>a[k]>>b[k];
deg[a[k]]++;}
for(i=1;i<=n;deg[i++]=0)
g[i]=(long*)malloc(deg[i]*sizeof(long));
for(j=1;j<=m;j++)
g[a[j]][deg[a[j]]++]=b[j];
ind=nr=ss=sq=0;
for(u=1;u<=n;u++)
if(c[u]==0)
tarjan(u,&nr,&ind);
y<<nr<<"\n";
r=q[sq--];
while(sq)
{r=q[sq--];
if(r==0)
y<<"\n";
else
y<<r<<" ";}
x.close();
y.close();
return 0;}