Pagini recente » Cod sursa (job #1619839) | Cod sursa (job #1734492) | Cod sursa (job #1206630) | Cod sursa (job #2194961) | Cod sursa (job #588469)
Cod sursa(job #588469)
#include<fstream.h>
#define N 100001
long n,m,i,j,k,a[2*N],b[2*N],deg[N]={0},*g[N],c[N]={0},nr,d[N],f[N],t,timp,q[2*N],p;
void parcurgere(long i)
{long j;
c[i]=2;
q[++p]=i;
for(j=deg[i]-1;j>=0;j--)
if(c[g[i][j]]==1)
parcurgere(g[i][j]);}
void colectare(long s,long v)
{c[s]=2,q[++p]=s;
parcurgere(v);
c[s]=1;}
void explorare(long i,long *timp,long *nr)
{long j;
d[i]=f[i]=(*timp)++;
c[i]=1;
for(j=deg[i]-1;j>=0;j--)
if(c[g[i][j]]==0)
{explorare(g[i][j],timp,nr);
if(f[i]>f[g[i][j]])
f[i]=f[g[i][j]];
if(d[i]<=f[g[i][j]])
{colectare(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];
deg[a[i]]++,deg[b[i]]++;}
for(j=1;j<=n;deg[j++]=0)
g[j]=(long*)malloc(deg[j]*sizeof(long));
for(k=1;k<=m;k++)
{g[a[k]][deg[a[k]]++]=b[k];
g[b[k]][deg[b[k]]++]=a[k];}
timp=p=nr=0;
for(i=1;i<=n;i++)
if(c[i]==0)
if(deg[i])
explorare(i,&timp,&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";}
x.close();
y.close();
return 0;}