Pagini recente » Cod sursa (job #1302769) | Cod sursa (job #766735) | Cod sursa (job #2973374) | Cod sursa (job #826924) | Cod sursa (job #2715044)
#include <iostream>
#include <list>
#include <stack>
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
class Graph{
int v;
list<int>* adj;
void sorttopo(int v, bool visited[], stack<int>& stack);
public:
//constructor
Graph(int v);
//to add edge in graph
void addEdge(int v, int w);
//to print topological sort
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);
}
//topsort
void Graph :: sorttopo(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])
sorttopo(*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)
{
sorttopo(i, visited, stack);
}
}
while(stack.empty() == false)
{
fout << stack.top() << " ";
stack.pop();
}
}
int main()
{
int n, m, x, y;
fin >> n >> m;
Graph g(n);
for(int i = 1; i <= m; i++)
{
fin >> x >> y;
g.addEdge(x, y);
}
g.topologicalSort();
return 0;
}