Pagini recente » Cod sursa (job #1671607) | Cod sursa (job #2405078) | Cod sursa (job #1416777) | Cod sursa (job #687018) | Cod sursa (job #2698276)
#include <iostream>
#include <list>
#include <stack>
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int N, M;
struct Graph {
int V;
list<int>* adj;
void topologicalSortUtil(int v, bool visited[], stack<int>& Stack);
Graph(int V);
void addEdge(int v, int w);
void topologicalSort();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V+1];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::topologicalSortUtil(int v, bool visited[], stack<int>& Stack)
{
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
Stack.push(v);
}
void Graph::topologicalSort()
{
stack<int> Stack;
bool* visited = new bool[V+1];
for (int i = 1; i <= V; i++)
visited[i] = false;
for (int i = 1; i <= V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
// Print
while (Stack.empty() == false) {
fout << Stack.top() << " ";
Stack.pop();
}
}
// Driver Code
int main()
{
fin >> N >> M;
// Create a graph given in the above diagram
Graph g(N);
int u, v;
for (int i = 0; i < M; i++) {
fin >> u >> v;
g.addEdge(u, v);
}
g.topologicalSort();
return 0;
}