Pagini recente » Cod sursa (job #619844) | Statistici Paula Nicoleta Gradu (Pauey) | Cod sursa (job #3290263) | Cod sursa (job #37043) | Cod sursa (job #3299086)
#include <bits/stdc++.h>
using namespace std;
void DFS(int i , vector<bool> & vis, const vector<vector<int>> & adj_lists, vector<int> & rev_path) {
if (vis[i] == true) {
return;
}
vis[i] = true;
for (int neigh : adj_lists[i]) {
DFS(neigh, vis, adj_lists, rev_path);
}
rev_path.push_back(i);
}
int main() {
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
int N, M;
fin >> N >> M;
// fout << "N = " << N << " and M = " << M << endl;
vector<vector<int>> adj_lists (N + 1);
vector<pair<int, int>> edges;
for (int i = 1; i <= M; i++) {
int a, b;
fin >> a >> b;
adj_lists[a].push_back(b);
edges.push_back(make_pair(a, b));
}
// Topo-sort on the graph
vector<bool> visited(N + 1);
vector<int> reversed_path;
// fout << "START" << endl;
for (int i = 1; i <= N; i++) {
// fout << "We start i = " << i << endl;
DFS(i, visited, adj_lists, reversed_path);
}
reverse(reversed_path.begin(), reversed_path.end());
// vector<int> positions (N + 1);
// for (int i = 0; i < N; i++) {
// positions[reversed_path[i]] = i + 1;
// }
// check conditions
// as some of them might be violated because we have cycles
// for (int i = 1; i <= M; i++) {
// if (positions[edges[i].first] >= positions[edges[i].second]) {
// }
// }
for (auto elem : reversed_path) {
fout << elem << " ";
}
fout << endl;
return 0;
}