Cod sursa(job #641147)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 27 noiembrie 2011 13:51:24
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

long n, m, a, b, i, niv[100010], niva[100010], viz[100010], cb, sk[100010], out[100010];
vector < long > g[200010], show[10000];

void df(long nod, long lev) {
	long aux = g[nod].size();
	niv[nod] = lev;
	viz[nod] = 1;
	niva[nod] = lev;

	sk[++sk[0]] = nod;
	for (long i = 0; i < aux; ++i) {
		if (viz[g[nod][i]] == 0) {
			df(g[nod][i], lev + 1);
			
			if (niva[g[nod][i]] < niva[nod]) 
				niva[nod] = niva[g[nod][i]];
			
			if (niva[g[nod][i]] >= niv[nod]) {				
				memset(out, 0, sizeof(out));
				
				while (sk[sk[0]] != g[nod][i]) {
					out[++out[0]] = sk[sk[0]];
					--sk[0];
				}
				
				--sk[0];
				out[++out[0]] = g[nod][i];
				out[++out[0]] = nod;
				
				sort(out + 1, out + out[0] + 1);
				
				++cb;
				for (long j = 1; j <= out[0]; ++j) 
					show[cb].push_back(out[j]);
			}
		} else {
			if (niva[nod] > niv[g[nod][i]] && (niv[g[nod][i]] + 1 != niv[nod])) {
				niva[nod] = niv[g[nod][i]];
			}
		}
	}
}

int main() {
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	
	scanf("%ld %ld", &n, &m);
	for (i = 1; i <= m; ++i) {
		scanf("%ld %ld", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	for (i = 1; i <= 100010; ++i) niv[i] = 2000000000;
	for (i = 1; i <= 100010; ++i) niva[i] = 2000000000;	
	df(1, 0);
	
	printf("%ld\n", cb);
	for (i = 1; i <= cb; ++i) {
		long aux = show[i].size();
		for (long j = 0; j < aux; ++j) 
			printf("%ld ", show[i][j]);
		printf("\n");
	}
	return 0;
}