Cod sursa(job #278624)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 12 martie 2009 13:44:40
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 105


int *g[N], *sol[N], mlr[N], level[N], use[N], nrcb = 0, n, m, u = 0;
struct stack{int x,y;} stiva[N];



void citire(), push(int, int), df(int, int), pmc(int, int), afisare();

int main (){
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    citire();

    level[0] = 0; use[1] = 1;
    df(1, 0);

    afisare();

    return 0;
}

void push(int a, int b){
    g[a][0]++;
    g[a] = (int *) realloc(g[a],(g[a][0] + 1) * sizeof(int));
    g[a][g[a][0]] = b;
}

void citire(){
int i, a, b;
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; i++){
	g[i] = (int *) malloc (sizeof(int));
	g[i][0] = 0;

	sol[i] = (int *) malloc (sizeof(int));
	sol[i][0] = 0;

    }
    for (i = 1; i <= m; i++){
	scanf("%d %d", &a, &b);
	push(a,b); push(b,a);
    }
}

void df(int nod, int tata){
int i, nnod;

    level[nod] = level[tata] + 1;
    mlr[nod] = level[nod];

    for (i = 1; i <= g[nod][0]; i++){
        nnod = g[nod][i];
        if (!use[nnod]){

	    use[nnod] = 1;
            stiva[++u].x = nod; stiva[u].y = nnod;
            df(nnod, nod);
	    if (mlr[nnod] < mlr[nod]) mlr[nod] = mlr[nnod];
	    if (mlr[nnod] >= level[nod]) pmc(nod, nnod);

        }
        else
            if (nnod != tata && mlr[nnod] < mlr[nod]) mlr[nod] = mlr[nnod];
    }
}

void pmc(int a, int b){
int m1, m2;
    nrcb++;
    do{

        m1 = stiva[u].x; m2 = stiva[u].y; u--;

        sol[nrcb][0]++;
        sol[nrcb] = (int*) realloc (sol[nrcb], (sol[nrcb][0] + 1) * sizeof(int));
        sol[nrcb][sol[nrcb][0]] = m2;

    } while ( m1 != a || m2 != b);

    sol[nrcb][0]++;
    sol[nrcb] = (int*) realloc (sol[nrcb], (sol[nrcb][0] + 1) * sizeof(int));
    sol[nrcb][sol[nrcb][0]] = m1;

}

void afisare(){
int i, j;
    printf("%d\n", nrcb);

    for (i = 1; i <= nrcb; i++){
        for (j = 1; j <= sol[i][0]; j++)
            printf("%d ", sol[i][j]);
        printf("\n");
    }
}