Pagini recente » Cod sursa (job #2850050) | Cod sursa (job #3170160) | Cod sursa (job #99339) | Cod sursa (job #2481667) | Cod sursa (job #3270733)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
void citire(std::vector<std::vector<int> > &graf, int &n) {
int m;
int i, j;
std::ifstream f("sortaret.in");
f >> n >> m;
graf.resize(n);
while (m--) {
f >> i >> j;
graf[i - 1].push_back(j - 1);
}
f.close();
}
void dfs(std::vector<std::vector<int> > &graf, std::vector<bool> &viz, std::stack<int> &s, std::vector<bool> &inStiva,
const int u) {
viz[u] = true;
for (const auto &v: graf[u])
if (!viz[v])
dfs(graf, viz, s, inStiva, v);
s.push(u + 1);
inStiva[u] = true;
}
void sortareTopologica() {
std::vector<std::vector<int> > graf;
int n;
citire(graf, n);
std::vector viz(n, false);
std::vector inStiva(n, false);
std::stack<int> s;
for (int i = 0; i < n; ++i)
if (!viz[i])
dfs(graf, viz, s, inStiva, i);
std::ofstream g("sortaret.out");
while (!s.empty()) {
const int u = s.top();
s.pop();
g << u << " ";
}
}
int main() {
sortareTopologica();
return 0;
}