Cod sursa(job #1181716)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 mai 2014 15:50:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.02 kb
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdexcept>
#include <stack>
#include <tuple>

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);

	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;
}

class DirectedGraph : public Graph
{

public:

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

	vector< vector<int> > getSCC();
};


vector< vector<int> > DirectedGraph::getSCC() {
	vector<vector<int> > components;
	if (vertexNumber == 0)
		return components;

	vector<bool> inStack(vertexNumber, false);
	vector< vector<int>::iterator > nextNode(vertexNumber);

	vector<int> inTime(vertexNumber, -1),
		lowlink(vertexNumber, -1), 
		who(vertexNumber, -1);


	stack<int> dfsStack, S;

	int indexCount = 0;
	for (int i = 0; i < vertexNumber; i++) {
		if (inTime[i] != -1) continue;
		dfsStack.push(i);
		while (!dfsStack.empty()) {
			int v = dfsStack.top();
			if (inTime[v] == -1) {
				S.push(v);
				inStack[v] = true;
				inTime[v] = lowlink[v] = indexCount++;
				nextNode[v] = begin(data[v]);
			} else 
			if (who[v] != -1) {
				auto& w = who[v];
				if (inStack[w])
					lowlink[v] = min(lowlink[v], lowlink[w]);
			}

			bool allDone = true;

			while (allDone && nextNode[v] != end(data[v])) {
				auto w = *(nextNode[v]++);
				if (inStack[w])
					lowlink[v] = min(lowlink[v], lowlink[w]);
				else
				if (allDone && inTime[w] == -1) {
					dfsStack.push(w);
					who[v] = w;
					allDone = false;
				}
			}


			if (allDone) {
				if (inTime[v] == lowlink[v]) {
					components.push_back(vector<int>());
					int w;
					do {
						w = S.top();
						inStack[w] = false;
						components.back().push_back(w);
						S.pop();
					} while (w != v);
				}
				dfsStack.pop();
			}
		}
	}

	return components;
}

void  DirectedGraph::addEdge(const int& x, const int& y) {
	data[x].push_back(y);
}
int main() {

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