Pagini recente » Cod sursa (job #429458) | Cod sursa (job #2531202) | Cod sursa (job #252923) | Cod sursa (job #2398230) | Cod sursa (job #3218173)
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
#define MAX_NR_NODES 50000
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
bitset<MAX_NR_NODES + 1> isVisited;
vector<int> graph[MAX_NR_NODES + 1];
stack<int> topologicalOrder;
void dfsTopoSort(int node) {
isVisited[node] = true;
int nrNeighbours = graph[node].size();
for (int i = 0; i < nrNeighbours; ++i) {
int neighbour = graph[node][i];
if (!isVisited[neighbour]) {
dfsTopoSort(neighbour);
}
}
topologicalOrder.push(node);
}
void createTopologicalSort(int nrNodes) {
for (int node = 1; node <= nrNodes; ++node) {
if (!isVisited[node]) {
dfsTopoSort(node);
}
}
}
void printTopologicalOrdering() {
while (!topologicalOrder.empty()) {
fout << topologicalOrder.top() << ' ';
topologicalOrder.pop();
}
}
int main() {
int nrNodes, nrDirectedEdges;
fin >> nrNodes >> nrDirectedEdges;
for (int directedEdge = 1; directedEdge <= nrDirectedEdges; ++directedEdge) {
int sourceNode, destinationNode;
fin >> sourceNode >> destinationNode;
graph[sourceNode].push_back(destinationNode);
}
createTopologicalSort(nrNodes);
printTopologicalOrdering();
return 0;
}