Pagini recente » Cod sursa (job #2632977) | Cod sursa (job #1860890) | Cod sursa (job #1529162) | Cod sursa (job #2645121) | Cod sursa (job #1315728)
/*
* =====================================================================================
*
* Filename: topological_sort_directed.cpp
*
* Description: Planning tasks, for example task 4 depends on 1, 2, then we
consider edges (4, 1), (4, 2).
*
* Version: 1.0
* Created: 01/12/2015 23:53:36
* Revision: none
* Compiler: gcc
*
* Author: YOUR NAME (),
* Organization:
*
* =====================================================================================
*/
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
vector<int> planning;
vector<vector<int> > graph;
vector<bool> visited;
void topologicalSort(int vertex)
{
stack<int> s;
vector<int> result;
s.push(vertex);
visited[vertex] = true;
while (!s.empty())
{
int element = s.top();
bool found = false;
int i;
for (i = 0; i < graph[element].size() && (!found); i++)
if (!visited[graph[element][i]])
found = true;
if (found)
{
i--;
s.push(graph[element][i]);
visited[graph[element][i]] = true;
}
else
{
s.pop();
planning.push_back(element); // put the nodes while I pop them out of the stack
}
} /* while */
}
int main(int argc, char** argv)
{
int n, m;
ifstream input("sortaret.in");
ofstream output("sortaret.out");
input >> n >> m;
for (int i = 0; i < n; i++)
{
vector<int> row;
graph.push_back(row);
visited.push_back(false);
}
for (int i = 0; i < m; i++)
{
int x, y;
input >> x >> y;
graph[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (!visited[i])
topologicalSort(i);
for (int i = planning.size() - 1; i >= 0; i--)
output << planning[i] << " ";
return 0;
}