Pagini recente » Cod sursa (job #1137077) | Cod sursa (job #31921) | Cod sursa (job #2582642) | Cod sursa (job #30819) | Cod sursa (job #1181554)
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdexcept>
#include <stack>
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();
int getVertexNumber() const;
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<int> getTopologicalSort();
};
vector<int> DirectedGraph::getTopologicalSort() {
vector<int> sortedOrder;
vector <bool> visited(vertexNumber, false);
vector< vector<int>::iterator > nextNode(vertexNumber);
stack<int> s;
for (int i = 0; i < vertexNumber; i++) {
if (!visited[i]) {
int v = i;
s.push(v);
while (!s.empty()) {
v = s.top();
if (!visited[v]) {
visited[v] = true;
nextNode[v] = begin(data[v]);
}
bool allDone = true;
while (allDone && nextNode[v] != end(data[v])) {
auto w = *(nextNode[v]++);
if (!visited[w]) {
s.push(w);
allDone = false;
}
}
if (allDone) {
sortedOrder.push_back(v);
s.pop();
}
}
}
}
reverse(begin(sortedOrder), end(sortedOrder));
return sortedOrder;
}
void DirectedGraph::addEdge(const int& x, const int& y) {
data[x].push_back(y);
}
int main() {
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
DirectedGraph G;
cin >> G;
vector<int> nodes = G.getTopologicalSort();
for (auto& x : nodes)
cout << x + 1 << " ";
return 0;
}