Pagini recente » Cod sursa (job #957994) | Cod sursa (job #452241) | Monitorul de evaluare | Cod sursa (job #1128463) | Cod sursa (job #3341605)
#include <fstream>
#include <vector>
#include <stack>
std::ifstream input ("sortaret.in");
std::ofstream output ("sortaret.out");
void dfs(std::vector<std::vector<int>>& graph, std::vector<int>& wasNodeVisited, std::stack<int>& outputStack, int startNode){
std::stack<int> nodeStack;
nodeStack.push(startNode);
wasNodeVisited[startNode] = true;
while(!nodeStack.empty()){
int currentNode = nodeStack.top();
bool validConnectionExistence = false;
for(auto node : graph[currentNode]){
if(!wasNodeVisited[node]){
nodeStack.push(node);
wasNodeVisited[node] = true;
validConnectionExistence = true;
}
}
if(!validConnectionExistence){
nodeStack.pop();
outputStack.push(currentNode);
}
}
}
int main () {
int n, m;
input >> n >> m;
std::vector<std::vector<int>> graph(n+1);
for(int i = 1; i <= m; i++){
int a, b;
input >> a >> b;
//a connects to b
graph[a].push_back(b);
}
std::vector<int> wasNodeVisited(n+1, false);
wasNodeVisited[0] = true;
std::stack<int> outputStack;
for(int i = 1; i <= n; i++){
if(!wasNodeVisited[i]){
dfs(graph, wasNodeVisited, outputStack, i);
}
}
while(!outputStack.empty()){
output << outputStack.top() << ' ';
outputStack.pop();
}
return 0;
}