Cod sursa(job #528113)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 2 februarie 2011 00:19:15
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#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;}