Pagini recente » Cod sursa (job #1336231) | Cod sursa (job #936239) | Cod sursa (job #1593114) | Cod sursa (job #207095) | Cod sursa (job #1315714)
/*
* =====================================================================================
*
* Filename: topological_sort_directed.cpp
*
* Description:
*
* 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<vector<int> > graph;
vector<bool> visited;
vector<int> 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();
result.push_back(element); // put the nodes while I pop them out of the stack
}
} /* while */
return result;
}
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);
}
vector<int> planning = topologicalSort(1);
for (int i = 0; i < planning.size(); i++)
output << planning[i] << " ";
return 0;
}