Cod sursa(job #280539)

Utilizator BaduBadu Badu Badu Data 13 martie 2009 13:55:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<stdio.h>
#include<string.h>
#define N 100010
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;
int S[5*N];
int D[N],L[N],ord,nr;
char viz[N];

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]=1;
	S[++ultim]=-1;
	memset(D,-1,sizeof(D));
	memset(L,-1,sizeof(L));
}

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

void Formeaza(int x,int y){
	nr++;
	int s1,s2;

	do{
		s1 = S[ultim--];
		s2 = S[ultim--];
		NOD *q= new NOD;
		q->x = s1;
		q->urm = C[nr];
		C[nr]=q;
		q=new NOD;
		q->x = s2;
		q->urm=C[nr];
		C[nr]=q;

	}while(s1!=x || s2!=y);

}


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]=nod;
				S[++ultim]=q->x;
			}
			if(D[q->x]==-1) {

				biconex(q->x,nod);

				L[nod] = min(L[nod],L[q->x]);
				if(L[q->x]>=D[nod]){
					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++){

		for(q=C[i];q;q=q->urm)viz[q->x]='1';

		for(q=C[i];q;q=q->urm)
		    if(viz[q->x]=='1'){
		       fprintf(g,"%d ",q->x);viz[q->x]='0';}
		fprintf(g,"\n");
	 }
	 return 0;
}