Pagini recente » Cod sursa (job #2019047) | Istoria paginii utilizator/suyggyu | Cod sursa (job #2016225) | Istoria paginii runda/bairam_aladin | Cod sursa (job #527943)
Cod sursa(job #527943)
#include<iostream.h>
#include<fstream.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,d[N][1001],c[N]={0},l[N],e[N],nr,f[N]={0};
void push(stack &s,long x)
{s.st[++s.sp]=x;}
long pop(stack &s)
{return s.st[s.sp--];}
void tarjan(long ind,long i,long nr)
{long k,j;
if(f[i]==0)
push(s,i);
f[i]=1;
c[i]=l[i]=ind;
for(j=deg[i]-1;j>=0;j--)
if(c[g[i][j]]==0&&f[g[i][j]]==0)
{tarjan(ind+1,g[i][j],nr);
push(s,g[i][j]);
if(l[i]>l[g[i][j]])
l[i]=l[g[i][j]];}
else
if(f[g[i][j]]==1&&l[i]>c[g[i][j]])
l[i]=c[g[i][j]];
if(c[i]==l[i])
{k=0;
while(s.sp!=0)
d[nr][++k]=pop(s);
e[nr]=k;}}
int main()
{ifstream f1("ctc.in");
ofstream f2("ctc.out");
f1>>n>>m;
for(k=1;k<=m;k++)
{f1>>a[k]>>b[k];
deg[b[k]]++;}
for(i=1;i<=n;i++)
{g[i]=(long*)malloc(deg[i]*sizeof(long));
deg[i]=0;}
for(j=1;j<=m;j++)
g[b[j]][deg[b[j]]++]=a[j];
ind=0;
nr=0;
for(i=1;i<=n;i++)
if(c[i]==0&&f[i]==0)
{s.sp=0;
nr++;
tarjan(ind,i,nr);}
f2<<nr<<endl;
for(j=1;j<=nr;j++)
{for(k=e[j];k>=1;k--)
f2<<d[j][k]<<" ";
f2<<endl;}
f1.close();
f2.close();
return 0;}