Pagini recente » Cod sursa (job #294756) | Cod sursa (job #2124425) | Cod sursa (job #1169657) | Cod sursa (job #2536556) | Cod sursa (job #606394)
Cod sursa(job #606394)
#include<fstream.h>
#define N 100001
long n,m,i,j,k,a[2*N],b[2*N],w[N],*g[N],c[N],nr,d[N],f[N],t,u,q[2*N],p;
void pa(long i)
{long j;
c[i]=2;
q[++p]=i;
for(j=w[i]-1;j>=0;j--)
if(c[g[i][j]]==1)
pa(g[i][j]);}
void co(long s,long v)
{c[s]=2,q[++p]=s;
pa(v);
c[s]=1;}
void ex(long i,long *u,long *nr)
{long j;
d[i]=f[i]=(*u)++;
c[i]=1;
for(j=w[i]-1;j>=0;j--)
if(!c[g[i][j]])
{ex(g[i][j],u,nr);
if(f[i]>f[g[i][j]])
f[i]=f[g[i][j]];
if(d[i]<=f[g[i][j]])
{co(i,g[i][j]);
q[++p]=0;
(*nr)++;}}
else
if(f[i]>d[g[i][j]])
f[i]=d[g[i][j]];}
int main()
{ifstream x("biconex.in");
ofstream y("biconex.out");
x>>n>>m;
for(i=1;i<=m;i++)
x>>a[i]>>b[i],w[a[i]]++,w[b[i]]++;
for(j=1;j<=n;w[j++]=0)
g[j]=(long*)malloc(w[j]*sizeof(long));
for(k=1;k<=m;k++)
g[a[k]][w[a[k]]++]=b[k],g[b[k]][w[b[k]]++]=a[k];
u=p=nr=0;
for(i=1;i<=n;i++)
if(!c[i])
if(w[i])
ex(i,&u,&nr);
else
c[i]=2,q[++p]=i,q[++p]=0,nr++;
y<<nr<<"\n";
t=q[p--];
while(p)
{t=q[p--];
if(t)
y<<t<<" ";
else
y<<"\n";}
return 0;}