Pagini recente » Cod sursa (job #2653695) | Cod sursa (job #2192718) | Cod sursa (job #342291) | Cod sursa (job #3194946) | Cod sursa (job #2972158)
#include <cstdio>
#include <memory>
#include <vector>
#include <algorithm>
using namespace std;
class Solver{
private:
int N, M;
vector<vector<int>> Graph;
vector<bool> used;
vector<int> solution;
public:
Solver() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
}
~Solver() {
fclose(stdin);
fclose(stdout);
}
void readData() {
scanf("%d%d", &N, &M);
Graph.resize(N);
used.resize(N);
int a, b;
for (int i = 0; i < M; ++i) {
scanf("%d%d", &a, &b);
--a; --b;
Graph[a].emplace_back(b);
}
}
void calculateTopologicalSort();
void DFS(int k);
void printSolution() {
reverse(solution.begin(), solution.end());
for (auto it: solution)
printf("%d ", it);
printf("\n");
}
};
void Solver::calculateTopologicalSort() {
for (int i = 0; i < N; ++i)
if (!used[i])
DFS(i);
}
void Solver::DFS(int k) {
used[k] = true;
for (auto it: Graph[k])
if(!used[it])
DFS(it);
solution.emplace_back(k + 1);
}
int main()
{
unique_ptr<Solver> s = make_unique<Solver>();
s->readData();
s->calculateTopologicalSort();
s->printSolution();
return 0;
}