Cod sursa(job #634457)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 16 noiembrie 2011 13:46:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <vector>
#include <bitset>
using namespace std;

#define nmax 100010

int n, m, k, vf=-1;
int nivel[nmax], nma[nmax];//nivelul minim de acces
bitset <nmax>viz;

struct nod{
   int a,b;
}stiva[nmax];

vector <int> lista[nmax], S[nmax];


void dfs(int nc) {
    viz[nc] = 1;
    nma[nc] = nivel[nc];

    for (vector <int>::iterator it = lista[nc].begin(); it != lista[nc].end(); ++it)//iau la rand toti vecinii lui nc/nod curent
        if (viz[*it] == 0){
            nivel[*it] = nivel[nc] + 1;
            vf++;
            stiva[vf].a = nc;
            stiva[vf].b = *it;
            dfs(*it);

            if (nma[*it] >= nivel[nc]) { //am gasit o componenta biconexa

                while (!(stiva[vf].a == nc && stiva[vf].b == *it)) {
                    S[k].push_back(stiva[vf].b);
                    vf--;
                }

                S[k].push_back(nc);
                S[k].push_back(*it);
                vf--;
 
                k++;
            }

            nma[nc] = min(nma[nc], nma[*it]);
        }
        else
            nma[nc] = min(nma[nc], nivel[*it]);
}

int main() {
    int i;    
    FILE *fin=fopen("biconex.in", "r");
    FILE *fout=fopen("biconex.out", "w");
    fscanf(fin,"%d %d", &n, &m);
    int a,b;
    for (i =0; i<m; i++) {
	fscanf(fin,"%d %d", &a, &b);
	lista[a].push_back(b);
	lista[b].push_back(a);
	}

    dfs(1);

   fprintf(fout,"%d\n", k);   
   for(i = 0; i <k; i++) {
	for (vector <int>::iterator it = S[i].begin(); it != S[i].end(); ++it)
		fprintf(fout,"%d ", *it);
	fprintf(fout,"\n");
	}

	return 0;
}