Cod sursa(job #771722)

Utilizator ioana26Ioana Andronescu ioana26 Data 26 iulie 2012 21:14:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
/*
Componentele biconexe dintr-un graf.
*/

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#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;
	while (u1 != u || v1 != v) {
		u1 = stiva.top().first;
		comp.push_back(u1);
		v1 = stiva.top().second;
		comp.push_back(v1);
		stiva.pop();
	} 
	comp_biconexe.push_back(comp);
}

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

int main(void) {
	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 < (int)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 < (int)comp_biconexe[i].size(); ++ j)
			printf("%d ", comp_biconexe[i][j]);
		printf("\n");
	}

	return 0;
}