Pagini recente » Cod sursa (job #685186) | Cod sursa (job #36099) | Cod sursa (job #1011234) | Cod sursa (job #1401821) | Cod sursa (job #528113)
Cod sursa(job #528113)
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#define N 100001
#define M 200001
typedef struct stack
{long st[N],sp;};
typedef struct nod
{long info;
struct nod *next,*prev;}Nod,*list;
typedef struct
{Nod *prim,*ultim;}deque;
stack s;
deque q,v[N];
long n,m,a[M],b[M],deg[N]={0},*g[N],k,i,j,t,ind,c[N]={0},l[N],nr,p;
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 addEnd(deque &q,long x)
{Nod *p=new Nod;
p->info=x;
p->next=p->prev=NULL;
if(q.prim==NULL)
q.prim=q.ultim=p;
else
{q.ultim->next=p;
p->prev=q.ultim;
q.ultim->next->prev=q.ultim;
q.ultim=q.ultim->next;}}
long delEnd(deque &q)
{Nod *p=q.ultim;
long x=q.ultim->info;
q.ultim=q.ultim->prev;
free(p);
if(q.ultim==NULL)
q.prim=NULL;
else
q.ultim->next=NULL;
return x;}
void tarjan(long i)
{long j,r;
c[i]=ind;
l[i]=ind;
ind++;
if(apartine(s,i)==0)
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])
{nr++;
v[nr].prim=v[nr].ultim=NULL;
if(s.sp!=0)
{while(s.sp!=0)
addEnd(v[nr],pop(s));}
else
addEnd(v[nr],i);}}
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];
nr=0;
ind=1;
s.sp=0;
for(i=1;i<=n;i++)
if(c[i]==0)
tarjan(i);
f2<<nr<<endl;
for(j=1;j<=nr;j++)
{while(v[j].prim!=NULL)
f2<<delEnd(v[j])<<" ";
f2<<endl;}
f1.close();
f2.close();
return 0;}