Pagini recente » Cod sursa (job #438985) | Cod sursa (job #2196539) | Cod sursa (job #497202) | Cod sursa (job #1349033) | Cod sursa (job #427320)
Cod sursa(job #427320)
#include<stdio.h>
FILE *f,*g;
long t[3][400100],i,n,m,x,y,c[100100],fin[100100],nr,z,q,parinte[100100],viz[100100],viz2[100100],nivel[100100],low[100100],nrcomp,nrr,cc[100100],tt[3][200100],maxim[100100];
void df(long k,long niv)
{ viz[k]=1; long p=c[k]; nivel[k]=niv; low[k]=niv;
while(p)
{ if(!viz[t[1][p]]) { parinte[t[1][p]]=k; df(t[1][p],niv+1); }
else if(nivel[t[1][p]]<nivel[k]&&parinte[k]!=t[1][p])
{ x=k; if(maxim[t[1][p]]<nivel[k]) maxim[t[1][p]]=nivel[k];
while(x!=t[1][p])
{ if(low[x]>nivel[t[1][p]]) low[x]=nivel[t[1][p]];
x=parinte[x];
}
}
p=t[2][p];
}
}
void dfc(long k)
{ viz2[k]=1; long p=c[k];
while(p)
{ if(!viz2[t[1][p]]) { if(low[t[1][p]]<=nivel[k]) dfc(t[1][p]); else { nrcomp++; nrr++; cc[nrcomp]=nrr; tt[1][nrr]=k; tt[2][nrr]=nrr+1; nrr++; tt[1][nrr]=t[1][p]; dfc(t[1][p]);}}
else if(parinte[k]!=t[1][p]&&nivel[t[1][p]]<nivel[k]&&maxim[t[1][p]]==nivel[k]&&low[k]==nivel[t[1][p]])
{ x=k; nrcomp++; nrr++; cc[nrcomp]=nrr;
while(x!=t[1][p])
{ tt[1][nrr]=x; nrr++; tt[2][nrr-1]=nrr;
x=parinte[x];
}
tt[1][nrr]=x;
}
p=t[2][p];
}
}
int main()
{ f=fopen("biconex.in","r"); g=fopen("biconex.out","w");
fscanf(f,"%ld%ld",&n,&m);
for(i=1;i<=m;i++)
{ fscanf(f,"%ld%ld",&x,&y);
if(c[x]==0) { nr++; c[x]=nr; t[1][nr]=y; fin[x]=nr; }
else { nr++; t[2][fin[x]]=nr; t[1][nr]=y; fin[x]=nr; }
z=x; x=y; y=z;
if(c[x]==0) { nr++; c[x]=nr; t[1][nr]=y; fin[x]=nr; }
else { nr++; t[2][fin[x]]=nr; t[1][nr]=y; fin[x]=nr; }
}
df(1,1);
dfc(1);
fprintf(g,"%ld\n",nrcomp);
for(i=1;i<=nrcomp;i++)
{ q=cc[i];
while(q) { fprintf(g,"%ld ",tt[1][q]); q=tt[2][q]; }
fprintf(g,"%\n");
}
fclose(g);
return 0;
}