Pagini recente » Cod sursa (job #1105593) | Cod sursa (job #1124691) | Cod sursa (job #229295) | Cod sursa (job #1668402) | Cod sursa (job #2324580)
#include <algorithm>
#include <fstream>
#include <iterator>
#include <vector>
void dfs(const int v,
std::vector<bool> &visited,
std::vector<int> &tsort,
const std::vector<std::vector<int>> &adj)
{
visited[v] = true;
for (int u : adj[v])
if (!visited[u])
dfs(u, visited, tsort, adj);
tsort.push_back(v + 1);
}
std::vector<int> get_tsort(const std::vector<std::vector<int>> &adj)
{
const int n = adj.size();
std::vector<bool> visited(n, false);
std::vector<int> tsort;
for (int v = 0; v < n; ++v)
if (!visited[v])
dfs(v, visited, tsort, adj);
return tsort;
}
int main()
{
std::ifstream fin("sortaret.in");
std::ofstream fout("sortaret.out");
int n, m;
fin >> n >> m;
int u, v;
std::vector<std::vector<int>> adj(n, std::vector<int>());
for (; m; m--)
{
fin >> u >> v;
adj[u - 1].push_back(v - 1);
}
auto tsort = get_tsort(adj);
std::reverse_copy(tsort.begin(), tsort.end(), std::ostream_iterator<int>(fout, " "));
fout << '\n';
return 0;
}