Pagini recente » Cod sursa (job #1223843) | Cod sursa (job #468664) | Cod sursa (job #2180745) | Istoria paginii utilizator/ovidiuandrus | Cod sursa (job #529675)
Cod sursa(job #529675)
#include<fstream.h>
#include<iostream.h>
#include<stdlib.h>
#define N 100001
#define M 200001
typedef struct nod
{long info;
struct nod *leg;}Nod,*list;
typedef struct stack
{long st[N],sp;};
stack s;
list q=NULL,d[N];
long n,m,a[M],b[M],deg[N]={0},*g[N],k,i,j,ind=0,c[N],l[N],nr;
void add(list &q,long x)
{Nod *p=new Nod;
p->info=x;
p->leg=q;
q=p;}
long pop(list &q)
{Nod *p=q->leg;
long x=q->info;
free(q);
q=p;
return x;}
int contine(list &q,long x)
{Nod *p;
for(p=q;p!=NULL;p=p->leg)
if(p->info==x)
return 1;
return 0;}
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 tarjan(long i,long *nr,long *ind)
{long j,r;
push(s,i);
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(apartine(s,g[i][j])==1&&l[i]>c[g[i][j]])
l[i]=c[g[i][j]];
if(c[i]==l[i])
{(*nr)++;
d[(*nr)]=NULL;
while(s.sp!=0)
{r=pop(s);
if(contine(q,r)==0)
if(r!=i)
{add(q,r);
add(d[(*nr)],r);}
else
break;
else
break;}
if(contine(q,i)==0)
{add(q,i);
add(d[(*nr)],i);}
if(d[(*nr)]==NULL)
{free(d[*nr]);
(*nr)--;}}}
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[a[k]]++;}
for(i=1;i<=n;i++)
{g[i]=(long*)malloc(deg[i]*sizeof(long));
deg[i]=0;
c[i]=0;}
for(j=1;j<=m;j++)
g[a[j]][deg[a[j]]++]=b[j];
ind=0;
nr=0;
s.sp=0;
q=NULL;
for(i=1;i<=n;i++)
if(c[i]==0)
tarjan(i,&nr,&ind);
f2<<nr<<endl;
for(j=1;j<=nr;j++)
{q=d[j];
while(q!=NULL)
f2<<pop(q)<<endl;
free(d[j]);
f2<<endl;}
f1.close();
f2.close();
return 0;}