Pagini recente » Cod sursa (job #780961) | Cod sursa (job #2465710) | Cod sursa (job #892089) | Istoria paginii runda/cei_mai_mari_olimpicari_runda_4/clasament | Cod sursa (job #1704143)
#include <iostream>
#include <stdio.h>
#include <deque>
#include <stack>
#include <vector>
#include <stdlib.h>
#include <set>
int main(){
FILE *in, *out;
in = fopen("sortaret.in", "r");
out = fopen("sortaret.out", "w");
int N, M;
fscanf(in, "%d %d", &N, &M);
std::vector<int> graf[N];
for (int i = 0; i < M; i++) {
int nod1, nod2;
fscanf(in, "%d %d", &nod1, &nod2);
graf[nod1 - 1].push_back(nod2 - 1);
}
std::stack<std::pair<bool, int> > dfStack;
std::vector<int> visited;
std::deque<int> endOrder;
std::set<int> setul;
for (int i = 0; i < N; i++) {
visited.push_back(0);
}
for (int i = 0; i < N; i++) {
if (visited[i] == 0) {
dfStack.push(std::make_pair(false, i));
while (!dfStack.empty()) {
std::pair<bool, int> nod = dfStack.top();
dfStack.pop();
if (nod.first) {
if (setul.insert(nod.second).second) {
endOrder.push_front(nod.second);
}
continue;
}
dfStack.push(std::make_pair(true, nod.second));
visited[nod.second] = 1;
for (unsigned int i = 0; i < graf[nod.second].size(); i++) {
if (visited[graf[nod.second][i]] == 0) {
dfStack.push(std::make_pair(false, graf[nod.second][i]));
}
}
}
}
}
for (unsigned int i = 0; i < endOrder.size(); i++) {
fprintf(out, "%d ", endOrder[i] + 1);
}
fclose(in);
fclose(out);
return 0;
}