Cod sursa(job #280324)

Utilizator BaduBadu Badu Badu Data 13 martie 2009 12:25:29
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<stdio.h>
#include<string.h>
#define N 100001
FILE *f=fopen("biconex.in","r");
FILE *g=fopen("biconex.out","w");

struct NOD {

	int x;
	NOD* urm;
};
NOD *G[N],*C[N];
int n,m,prim,ultim;
struct pct{ int t,f; };
pct S[5*N];
int D[N],L[N],ord,nrfii,nr;


void ADD(NOD*&p,int catre){

	NOD *q= new NOD;
	q->urm=p;
	q->x=catre;
	p=q;
}

void date(){
	int x,y;
	fscanf(f,"%d%d",&n,&m);
	for(;m--;){ fscanf(f,"%d%d",&x,&y);ADD(G[x],y);ADD(G[y],x); }
	S[++ultim].f=1;
	S[ultim].t =-1;
	memset(D,-1,sizeof(D));
	memset(L,-1,sizeof(L));
}

inline min(int a,int b){ return (a<b?a:b); }

void Formeaza(int x,int y){
	pct p;
	do{
		p = S[ultim--];
		ADD(C[nr],p.t);
		//ADD(C[nr],p.f);
	}while(p.t != y || p.f != x);
	NOD*q = new NOD;
	q = C[nr];
        if(q->urm->urm==NULL) ADD(C[nr],p.f);
}


void biconex(int nod, int tnod){

	D[nod]=L[nod]=++ord;
	NOD*q = new NOD;
	q = G[nod];
	for(;q;q=q->urm){
		if(q->x != tnod && D[q->x]<D[nod]){

				S[++ultim].t=nod;
				S[ultim].f=q->x;
			}
			if(D[q->x]==-1) {
				if(nod==1) nrfii++;
				biconex(q->x,nod);

				L[nod] = min(L[nod],L[q->x]);
				if(L[q->x]>=D[nod]){
					nr++;
					Formeaza(q->x,nod);

				}
			}else{
				if(q->x != tnod) L[nod]=min(L[nod],D[q->x]);
			     }
		}
	}

int main(){

	 date();
	 biconex(1,-1);
	 fprintf(g,"%d\n",nr);
	 NOD*q = new NOD;
	 for(int i=1;i<=nr;i++){
		q = C[i];
		for(;q;q=q->urm) fprintf(g,"%d ",q->x);
		fprintf(g,"\n");
	 }
	 return 0;
}