Cod sursa(job #296180)

Utilizator savimSerban Andrei Stan savim Data 4 aprilie 2009 13:22:42
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_N 100010

int n, m, i, p, q, k, sol;
int fol[MAX_N], niv[MAX_N], tata[MAX_N], c[MAX_N];
int stiv[MAX_N][2];
vector <int> A[MAX_N], S[MAX_N];

void cit() {
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d %d", &p, &q);
		A[p].push_back(q);
		A[q].push_back(p);
	}
}

void dfs(int nod) {
	fol[nod] = 1;

	//c[i] = nivelul minim la care pot ajunge din subarborele lui i
	c[nod] = niv[nod];

	int len = A[nod].size();

	for (int i = 0; i < len; i++) {
		int son = A[nod][i];
		if (!fol[son]) {
			tata[son] = nod;
			niv[son] = niv[nod] + 1;

            stiv[++k][0] = nod;
			stiv[k][1] = son;
			
			dfs(son);
				
			if (c[nod] > c[son]) c[nod] = c[son];

			//am gasit o componenta biconexa
			if (c[son] >= niv[nod]) {
				sol++;
			    while (!(stiv[k][0] == nod && stiv[k][1] == son)) {
					 S[sol].push_back(stiv[k][0]);
					 S[sol].push_back(stiv[k][1]);
					 k--;
				}
				S[sol].push_back(stiv[k][0]);
			    S[sol].push_back(stiv[k][1]);

				k--;
			}
		}
		else if (tata[nod] != son && niv[son] < niv[nod]) {
		     	 if (c[nod] > niv[son]) c[nod] = niv[son];

				 stiv[++k][0] = nod;
				 stiv[k][1] = son;
		     }
	}
}

void write() {
	printf("%d\n", sol);
              
	for (i = 1; i <= sol; i++) {
		sort(S[i].begin(), S[i].end());

		int len = S[i].size();
		for (int j = 0; j < len; j++)
			if ((j < len - 1 && S[i][j] != S[i][j + 1]) || j == len - 1)
				printf("%d ", S[i][j]);
		printf("\n");
	}
}

int main() {

    cit();

	//fac arborele DF al grafului
    dfs(1);

	write();

	return 0;
}