Cod sursa(job #820534)

Utilizator unholyfrozenCostea Andrei unholyfrozen Data 20 noiembrie 2012 23:37:35
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 3.43 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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

class graph {
	const int num_nodes;
	vector<int>* Edges;

public:
	graph(int num_nodes) : num_nodes(num_nodes) {
		Edges = new vector<int>[num_nodes];
	}

	~graph() {
		delete[] Edges;
	}
	
	void add_edge(int node_1, int node_2) {
		Edges[node_1].push_back(node_2);
		Edges[node_2].push_back(node_1);
	}
	
	void level_dfs(int node, int* Level, int* min_level_reached, int* through_children, vector<int>* children, int* father, int cur_level) {
		Level[node] = cur_level;
		min_level_reached[node] = Level[node] + 1;
		through_children[node] = Level[node];

		for (vector<int>::iterator it = Edges[node].begin(); it != Edges[node].end(); it++)
			if (father[*it] != -1 && Level[*it] < min_level_reached[node])
				min_level_reached[node] = Level[*it]; 	

		for (vector<int>::iterator it = Edges[node].begin(); it != Edges[node].end(); it++)
			if (father[*it] == -1) {
				/* new children */
				father[*it] = node;
				children[node].push_back(*it);
				level_dfs(*it, Level, min_level_reached, through_children, children, father, cur_level + 1);
				if (through_children[node] > MIN(min_level_reached[*it], through_children[*it]))
					through_children[node] = MIN(min_level_reached[*it], through_children[*it]);
			}
	}

	void get_biconex_comp(int node, int* through_children, int *min_level_reached, vector<int>* children, vector<vector<int> >& comp_biconex, vector<int>& stack, int cur_lvl) {
		for (vector<int>::iterator it = children[node].begin(); it != children[node].end(); it++) {
			get_biconex_comp(*it, through_children, min_level_reached, children, comp_biconex, stack, cur_lvl + 1);
			if (through_children[*it] >= cur_lvl && min_level_reached[*it] >= cur_lvl) {
				/* start a new comp biconex */
				stack.push_back(node);
				comp_biconex.push_back(stack);
				stack.clear();
			}
		}
		stack.push_back(node);
	}

	void print_biconex() {
		int* Level = new int[num_nodes];
		int* min_level_reached = new int[num_nodes], *through_children = new int[num_nodes];
		vector<int>* children = new vector<int>[num_nodes];
		int* father = new int[num_nodes];
		vector<vector<int> > comp_biconex;
		vector<int> stack;
		
		for (int i = 0; i < num_nodes; i++) 
			father[i] = -1;
		
		for (int i = 0; i < num_nodes; i++)
		if (father[i] == -1) {
			father[i] = i;
			level_dfs(i, Level, min_level_reached, through_children, children, father, 0);
			
			get_biconex_comp(i, through_children, min_level_reached, children, comp_biconex, stack, 0); 			
		}
		
		
		printf("%d\n", comp_biconex.size());
		for(vector<vector<int> >::iterator vec_it = comp_biconex.begin(); vec_it != comp_biconex.end(); vec_it++) {
			for(vector<int>::iterator it = vec_it->begin(); it != vec_it->end(); it++)
				if (it != vec_it->begin())
					printf(" %d", (*it) + 1);
				else
					printf("%d", (*it) + 1);
			printf("\n");
		}

		delete[] Level;
		delete[] min_level_reached;
		delete[] children;
		delete[] father;
	}
};
int main()
{
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	
	int num_nodes, num_edges;
	scanf("%d %d", &num_nodes, &num_edges);
//	num_nodes = 8;
	graph G(num_nodes);

	for (int i = 0; i < num_edges; i++) {
		int node_1, node_2;

		scanf("%d %d", &node_1, &node_2);
		G.add_edge(node_1 - 1, node_2 - 1);		
	}

	G.print_biconex();	

	return 0;
}