Cod sursa(job #286592)

Utilizator razyelxrazyelx razyelx Data 23 martie 2009 22:25:36
Problema Componente biconexe Scor 58
Compilator cpp Status done
Runda Arhiva educationala Marime 2.47 kb
#include <fstream.h>
#include <stdlib.h>
#define Nmax 100001
#define Mmax 200001
ifstream in("biconex.in");
ofstream out("biconex.out");

struct muchie{int x,y;} ST[Mmax];

int vf,n,m,num,cb,nrfii;
int DFN[Nmax],LOW[Nmax];
int * A[Nmax], art[Nmax], *c[Nmax];
void initializare(){
     for(int i=1;i<=n;++i)DFN[i] = LOW[i] = -1;
     ST[0].x = 1; ST[0].y = -1;
}
void citire(){
     int x,y,i;

     in>>n>>m;
     for(i=1;i<=n;++i){
	A[i] = (int *)realloc(A[i], sizeof(int));
	A[i][0] = 0;
	c[i] = (int *)realloc(c[i], sizeof(int));
	c[i][0] = 0;
     }
     for(i=1;i<=m;++i){
	in>>x>>y;
	A[x][0]++;
	A[x] = (int *)realloc(A[x], (A[x][0]+1)*sizeof(int));
	A[x][A[x][0]] = y;

	A[y][0]++;
	A[y] = (int *)realloc(A[y], (A[y][0]+1)*sizeof(int));
	A[y][A[y][0]] = x;
     }
}
int min(int x,int y){
    if(x>y) return y;
    return x;
}
void salveaza(int x, int y){
     muchie p;

     do{
	 p = ST[vf--];
	 if(p.x!=x && p.x != y){
	   c[cb][0]++;
	   c[cb] = (int *)realloc(c[cb],(c[cb][0]+1)*sizeof(int));

	   c[cb][c[cb][0]] = p.x;
	 }

     }while(p.x!=x || p.y!=y);

     c[cb][0]++;
     c[cb] = (int *)realloc(c[cb],(c[cb][0]+1)*sizeof(int));
     c[cb][c[cb][0]] = x;
     c[cb][0]++;
     c[cb] = (int *)realloc(c[cb],(c[cb][0]+1)*sizeof(int));
     c[cb][c[cb][0]]   = y;

}
void comp_biconexe(int u, int tu){
     int d; // descendent
     DFN[u] = LOW[u] = ++num;
     for(int i=1;i<=A[u][0];++i){
	d = A[u][i];

	if(d!=tu && DFN[d] < DFN[u]) // daca nu a mai fost vizitat
	  ST[++vf].x = d,ST[vf].y=u;  // sau daca este muchie de intoarcere

	if(DFN[d] == -1){ // daca nu a mai fost vizitat
	    if(u == 1) // daca u este radacina inseamna ca este un fiu al radacinii
	      nrfii++;
	    comp_biconexe(d,u);  // parcurgere dfs
	    LOW[u] = min(LOW[u],LOW[d]); // se atribuie recursiv fiecarui nod u care are legatura cu x nodul cu deep-breath number(dfn) cel mai mic
	    if(LOW[d] >= DFN[u]){// nu exista muchie de la x la un stramos a lui u
				 // este punct de art
	      if(u!=1)art[u] = 1;
	      cb++;
	      salveaza(d,u);

	    }
	}
	else if(d!=tu) // nu a mai fost vizitat => muchie de intoarce de la u la x
		 LOW[u] = min(LOW[u],DFN[d]);

     }
}
void afisare(){
     int i,j;
     out<<cb<<"\n";

     for(i=1;i<=n;++i){
	for(j=1;j<=c[i][0];++j)
	   out<<c[i][j]<<" ";
	out<<"\n";
     }
}

int main(){
    citire();
    initializare();
    comp_biconexe(1,-1);
    afisare();
    return 0;
}