Cod sursa(job #2768750)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 12 august 2021 08:14:04
Problema Componente biconexe Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100001
int p,u,n,m,i,a[2*N],b[2*N],w[N],*g[N],c[N],r,d[N],f[N],q[10*N];
void P(int i)
{
	c[i]=2,q[++p]=i;
	for(int j=w[i]-1;j>=0;--j)
        if(c[g[i][j]]==1)
            P(g[i][j]);
}
void E(int i)
{
	d[i]=f[i]=u++,c[i]=1;
	for(int j=w[i]-1;j>=0;--j)
        if(!c[g[i][j]]) {
            E(g[i][j]);
            if(f[i]>f[g[i][j]])
                f[i]=f[g[i][j]];
            if(d[i]<=f[g[i][j]])
                c[i]=2,q[++p]=i,P(g[i][j]),c[i]=1,q[++p]=0,r++;
        } else if(f[i]>d[g[i][j]])
            f[i]=d[g[i][j]];
}
int main()
{
	freopen("biconex.in","r",stdin),freopen("biconex.out","w",stdout),scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
    	scanf("%d%d",a+i,b+i),++w[a[i]],++w[b[i]];
	for(i=1;i<=n;w[i++]=0)
    	g[i]=(int*)malloc(w[i]*sizeof(int));
	for(i=1;i<=m;++i)
    	g[a[i]][w[a[i]]++]=b[i],g[b[i]][w[b[i]]++]=a[i];
	for(i=1;i<=n;++i)
        if(!c[i])
            if(w[i])
                E(i);
            else
                c[i]=2,q[++p]=i,q[++p]=0,++r;
	printf("%d\n",r);
	for(--p;p;--p)
        if(q[p])
            printf("%d ",q[p]);
        else
            printf("\n");
    return 0;
}