Pagini recente » Cod sursa (job #148803) | Cod sursa (job #1515710) | Cod sursa (job #2331991) | Cod sursa (job #1019361) | Cod sursa (job #2370218)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");
class Graph
{
private:
int m_vertices;
std::vector<std::vector<int>>V;
public:
Graph(int vertices)
: m_vertices(vertices)
{
V.resize(m_vertices+1);
}
void AddEdge(int where, int what)
{
V[where].push_back(what);
}
void Print()
{
std::vector<int>::iterator it;
for (int i = 1; i <= m_vertices; i++)
{
out << i << ": ";
for (it = V[i].begin(); it != V[i].end(); it++)
{
out << (*it) << " ";
}
out << '\n';
}
}
void TopologicalSort();
void TopSortUtility(int vertex, std::stack<int>& Stack, bool Visited[]);
};
void Graph::TopSortUtility(int vertex, std::stack<int>& Stack, bool Visited[])
{
Visited[vertex] = true;
int i;
for (i = 0; i < V[vertex].size(); i++)
{
if (!Visited[V[vertex][i]])
TopSortUtility(V[vertex][i], Stack, Visited);
}
Stack.push(vertex);
}
void Graph::TopologicalSort()
{
std::stack<int> Stack;
bool* Visited = new bool[m_vertices];
for (int i = 1; i <= m_vertices; i++)
{
Visited[i] = false;
}
for (int i = 1; i <= m_vertices; i++)
{
if (!Visited[i])
TopSortUtility(i, Stack, Visited);
}
while (!Stack.empty())
{
out << Stack.top() << " ";
Stack.pop();
}
}
int main()
{
int n, m;
in >> n >> m;
Graph G(n);
int v1, v2;
for (int i = 0; i < m; i++)
{
in >> v1 >> v2;
G.AddEdge(v1, v2);
}
G.TopologicalSort();
//G.Print();
}