Cod sursa(job #1181549)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 mai 2014 02:39:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.04 kb
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdexcept>
#include <stack>

#pragma once

using namespace std;

class Graph
{
protected:

	int vertexNumber;
	int edgeNumber;

	vector< vector<int> > data;

	virtual void readData(istream& in);

	virtual void writeData(ostream& out);

public:

	Graph(int vertexNumber_);

	Graph(int vertexNumber_, int edgeNumber, const vector< pair<int, int> >& edges);

	virtual ~Graph();

	virtual void addEdge(const int&x, const int& y);

	vector< vector<int> > getBiconnectedComponents();

	friend istream& operator >> (istream& in, Graph& graph);

	friend ostream& operator << (ostream& out, Graph& graph);

};

Graph::Graph(int vertexNumber_ = 0) {
	vertexNumber = vertexNumber_;
	data.resize(vertexNumber);
}

Graph::Graph(int vertexNumber_, int edgeNumber_, const vector< pair<int, int> >& edges) {
	vertexNumber = vertexNumber_;
	edgeNumber = edgeNumber_;
	data.resize(vertexNumber);
	for (const auto& edge : edges) {
		addEdge(edge.first, edge.second);
	}
}

Graph::~Graph() {
	vertexNumber = 0;
}

void Graph::addEdge(const int& x, const int& y) {
	try {
		if (x < 0 || x >= vertexNumber || y < 0 || y >= vertexNumber) {
			out_of_range outException("Node index out of bounds!");
			throw outException;
		}
		data[x].push_back(y);
		data[y].push_back(x);
	}

	catch (out_of_range& exception) {
		cout << exception.what() << "\n";
	}
}

void Graph::readData(istream& in) {
	in >> vertexNumber >> edgeNumber;
	data.clear();
	data.resize(vertexNumber);
	int a, b;
	for (int i = 0; i < edgeNumber; i++) {
		in >> a >> b;
		a--, b--;
		addEdge(a, b);
	}
}

void Graph::writeData(ostream& out) {
	out << vertexNumber << " " << edgeNumber << "\n";
	for (int v = 0; v < vertexNumber; v++) {
		for (const int& w : data[v]) {
			if (v < w) {
				out << v << " " << w << "\n";
			}
		}
	}
}


istream& operator >> (istream& in, Graph& graph) {
	graph.readData(in);
	return in;
}

ostream& operator << (ostream& out, Graph& graph) {
	graph.writeData(out);
	return out;
}

vector< vector<int> > Graph::getBiconnectedComponents() {
	vector<vector<int> > components;
	if (vertexNumber == 0)
		return components;

	vector<bool> visited(vertexNumber, false);
	vector<int> parent(vertexNumber, -1),
		depth(vertexNumber, numeric_limits<int>::max()),
		minSDepth(vertexNumber, numeric_limits<int>::max());

	vector< vector<int>::iterator > nextNode(vertexNumber);
	const int root = 0;
	stack<int> s;
	stack< pair<int, int> > edgeStack;
	s.push(root);
	depth[root] = 0;

	while (!s.empty()){
		int x = s.top();
		s.pop();
		if (!visited[x]){
			visited[x] = true;
			minSDepth[x] = depth[x];
			nextNode[x] = begin(data[x]);
		} else {
			auto y = *(nextNode[x]++);
			pair<int, int> edge;
			minSDepth[x] = min(minSDepth[x], minSDepth[y]);
			if (minSDepth[y] >= depth[x]) {
				components.push_back(vector<int>());
				do {
					edge = edgeStack.top();
					edgeStack.pop();
					components.back().push_back(edge.first);
					components.back().push_back(edge.second);
				} while (x != edge.first || y != edge.second);
			}
		}

		for (auto& it = nextNode[x]; it != end(data[x]); it++) {
			auto& y = *it;
			if (visited[y]) {
				if (parent[x] != y)
					minSDepth[x] = min(minSDepth[x], depth[y]);
			} else {
				s.push(x);
				s.push(y);
				edgeStack.push({ x, y });
				parent[y] = x;
				depth[y] = depth[x] + 1;
				break;
			}
		}
	}

	for (auto& component : components) {
		sort(component.begin(), component.end());
		component.erase(unique(component.begin(), component.end()), component.end());
	}

	return components;
}

int main() {

	ifstream cin("biconex.in");
	ofstream cout("biconex.out");
	Graph G;
	cin >> G;
	vector< vector< int> > components = G.getBiconnectedComponents();
	cout << components.size() << "\n";
	for (auto& nodes : components) {
		for (auto& x : nodes) cout << x + 1 << " ";
		cout << "\n";
	}
	return 0;
}