Pagini recente » Cod sursa (job #2127759) | Cod sursa (job #1623216) | Cod sursa (job #1787842) | Cod sursa (job #1948868) | Cod sursa (job #1734739)
#include <iostream>
#include <set>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int noLines, noNodes;
class Node
{
public:
int value;
vector<Node*>* adjList;
Node(int value) { this->value = value; adjList = NULL; }
};
set<int> visited;
stack<int> topologic;
vector<Node*>* graph;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
void depth_first(int node)
{
for (int i = 0; i < graph->at(node)->adjList->size(); i++)
{
int nextValue = graph->at(node)->adjList->at(i)->value;
if (visited.find(nextValue) == visited.end())
{
visited.insert(nextValue);
depth_first(nextValue);
topologic.push(nextValue);
}
}
}
int main()
{
fin >> noNodes >> noLines;
graph = new vector<Node*>(noNodes+1);
graph->at(0) = new Node(-1);
for (int i = 1; i <= noNodes; i++)
{
graph->at(i) = new Node(i);
graph->at(i)->adjList = new vector<Node*>();
}
int start, end;
for (int i = 0; i < noLines; i++)
{
fin >> start >> end;
graph->at(start)->adjList->push_back(graph->at(end));
}
while(topologic.size() < noNodes)
{
for (int i = 1; i <= noNodes; i++)
if(visited.find(i) == visited.end())
{
visited.insert(i);
depth_first(i);
topologic.push(i);
}
}
while(topologic.size() > 0)
{
fout << topologic.top() << ' ';
topologic.pop();
}
//cin.get();
//cin.get();
}