Pagini recente » Cod sursa (job #472036) | Cod sursa (job #2662920) | Cod sursa (job #2321728) | Cod sursa (job #3221321) | Cod sursa (job #528124)
Cod sursa(job #528124)
#include<stdio.h>
#include<stdlib.h>
#define N 100001
#define M 200001
typedef struct stack
{long st[N],sp;};
stack s;
long n,m,a[M],b[M],deg[N]={0},*g[N],k,i,j,t,ind=0,c[N]={0},l[N],nr=0,p,e[N],*d[N],f[N];
void push(stack &s,long x)
{s.st[++s.sp]=x;}
long pop(stack &s)
{return s.st[s.sp--];}
int apartine(stack &s,long x)
{long i;
for(i=1;i<=s.sp;i++)
if(s.st[i]==x)
return 1;
return 0;}
void dfs(long i)
{long j,r;
for(j=deg[i]-1;j>=0;j--)
if(c[g[i][j]]==0)
dfs(g[i][j]);}
void tarjan(long i)
{long j,r;
c[i]=ind;
l[i]=ind;
ind++;
push(s,i);
for(j=deg[i]-1;j>=0;j--)
if(c[g[i][j]]==0)
{tarjan(g[i][j]);
if(l[i]>l[g[i][j]])
l[i]=l[g[i][j]];}
else
if(apartine(s,g[i][j])==1&&l[i]>c[g[i][j]])
l[i]=c[g[i][j]];
if(c[i]==l[i])
{do
{r=pop(s);
printf("%ld ",r);}
while(r!=i);}}
int main()
{freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(k=1;k<=m;k++)
{scanf("%ld%ld",&a[k],&b[k]);
deg[b[k]]++;}
for(i=1;i<=n;i++)
{g[i]=(long*)malloc((deg[i]+1)*sizeof(long));
deg[i]=0;
f[i]=0;}
for(k=1;k<=m;k++)
g[b[k]][deg[b[k]]++]=a[k];
nr=0;
for(i=1;i<=n;i++)
if(c[i]==0)
{dfs(i);
nr++;}
printf("%ld\n",nr);
for(j=1;j<=n;j++)
c[j]=0;
for(k=1;k<=n;k++)
if(c[k]==0)
tarjan(k);
fclose(stdin);
fclose(stdout);
return 0;}