Mai intai trebuie sa te autentifici.
Cod sursa(job #2930537)
| Utilizator | Data | 28 octombrie 2022 17:12:48 | |
|---|---|---|---|
| Problema | Sortare topologica | Scor | 10 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.81 kb |
#include <bits/stdc++.h>
using namespace std;
vector<int> topsort(const vector<vector<int>>& adj) {
vector<int> ans;
vector<bool> visited(adj.size(), 0);
function<void(int)> dfs = [&](int current) {
visited[current] = 1;
for (int neigh : adj[current])
dfs(neigh);
ans.push_back(current);
};
for (size_t i = 0; i < adj.size(); ++i)
if (!visited[i])
dfs(i);
reverse(ans.begin(), ans.end());
return ans;
}
int main() {
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m;
fin >> n >> m;
vector<vector<int>> adj(n);
for (int i = 1, x, y; i <= m; ++i) {
fin >> x >> y;
adj[x - 1].push_back(y - 1);
}
for (int x : topsort(adj))
fout << x + 1 << ' ';
fout << '\n';
}
