Cod sursa(job #820516)

Utilizator unholyfrozenCostea Andrei unholyfrozen Data 20 noiembrie 2012 22:54:31
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.11 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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

public:
	graph(int num_nodes) {
		this->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[father[*it]] < min_level_reached[node])
				min_level_reached[node] = level[father[*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_level_reached[*it])
					through_children[node] = min_level_reached[*it];
			}
	}

	void get_biconex_comp(int node, int* through_children, 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, children, comp_biconex, stack, cur_lvl + 1);
			if (through_children[*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[num_nodes];
		int min_level_reached[num_nodes], through_children[num_nodes];
		vector<int> children[num_nodes];
		int father[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, 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++)
				printf("%d ", (*it) + 1);
			printf("\n");
		}
	}
};
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 = 4;
	graph G(num_nodes);
	
	G.add_edge(0, 1);
	G.add_edge(0, 2);
	G.add_edge(0, 3);
/*	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;
}