Cod sursa(job #1472471)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 09:03:14
Problema Componente biconexe Scor 46
Compilator c Status done
Runda Arhiva educationala Marime 1.07 kb
#include<stdio.h>
#include<stdlib.h>
int p,u,n,m,i,a[200002],b[200002],w[100001],*g[100001],c[100001],r,d[100001],f[100001];
char q[200002];
void P(int i) {
	c[i]=2,q[++p]=i+'0';
	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+'0',P(g[i][j]),c[i]=1,q[++p]='\n',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+'0',q[++p]='\n',r++;
	printf("%d\n",r);
	for(p--;p;p--)
        printf("%c ",q[p]);
}