Cod sursa(job #771652)

Utilizator ioana26Ioana Andronescu ioana26 Data 26 iulie 2012 18:48:31
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
/*
Componentele biconexe dintr-un graf.
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <stdio.h>

#define MAXN	100001

#define min(a, b) (a < b ? a : b)

using namespace std;

int nr_noduri, nr_muchii;
vector <int> graf[MAXN], nivel, low;
vector <vector <int> > comp_biconexe;
stack <pair <int, int> > stiva;
 
void componenta (int u, int v) {
	vector <int> comp; 
	int u1, v1;
	do {
		u1 = stiva.top().first;
		comp.push_back(u1);
		v1 = stiva.top().second;
		comp.push_back(v1);
		stiva.pop();
	} while (u1 != u || v1 != v);
	comp_biconexe.push_back(comp);
}

void dfs (int u, int t, int idx) {
	nivel[u] = low[u] = idx;
	for (int v = 0; v < graf[u].size(); v++) {
		if (graf[u][v] == t)
			continue;
		if (nivel[graf[u][v]] < 0) {
			stiva.push(make_pair(u, graf[u][v]));
			dfs(graf[u][v], u, idx++);
			low[u] = min(low[u], low[graf[u][v]]);
			
			if (low[graf[u][v]] >= nivel[u])
				componenta(u, graf[u][v]);
		}
		else
			low[u] = min(low[u], nivel[graf[u][v]]);
	}
}

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

	int i, j, x, y;
	scanf("%d %d", &nr_noduri, &nr_muchii);
	for (i = 0; i < nr_muchii; i++) {
		scanf("%d %d", &x, &y);
		graf[x].push_back(y);
		graf[y].push_back(x);
	}	

	nivel.resize(nr_noduri + 1);
	nivel.assign(nr_noduri + 1, -1);
	low.resize(nr_noduri + 1);
	dfs(1, 0, 0);
	
	printf("%d\n", comp_biconexe.size());
	for (i = 0; i < comp_biconexe.size(); i++) {
		sort(comp_biconexe[i].begin(), comp_biconexe[i].end());
		comp_biconexe[i].erase(unique(comp_biconexe[i].begin(), comp_biconexe[i].end()), comp_biconexe[i].end());
		for (j = 0; j < comp_biconexe[i].size(); j++)
			printf("%d ", comp_biconexe[i][j]);
		printf("\n");
	}
	
	return 0;
}