Pagini recente » Cod sursa (job #1747181) | Cod sursa (job #1285512) | Cod sursa (job #2748549) | Cod sursa (job #636158) | Cod sursa (job #2780130)
#include <iostream>
#include <list>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
class Graph {
int V;
list<int>* adj;
void topologicalSortUtil(int v, bool visited[], stack<int>& Stack);
public:
Graph(int V);
void addEdge(int v, int w);
void topologicalSort();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
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];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
while (Stack.empty() == false) {
fout << Stack.top()+1 << " ";
Stack.pop();
}
}
int main()
{
int n,m;
fin>>n>>m;
int x,y;
Graph g(n);
for(int i=1;i<=m;i++)
{
fin>>x>>y;
g.addEdge(x-1,y-1);
}
g.topologicalSort();
return 0;
}