Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <algorithm>
- #include <iostream>
- using namespace std;
- const int MAXN = 10000; // максимальное количество верщин
- int n; // число вершин
- vector<vector<int>> g(MAXN); // граф
- vector<bool> used (MAXN, false); // массив индикации
- vector<int> ans; // массив ответа
- void dfs(int cur) { // почти стандартный dfs, просто добавляем вершины в ответ после их обработки
- used[cur] = true;
- for(auto now : g[cur]){
- //cout << cur + 1 << " " << now + 1 << '\n'; если нужно увидеть какие ребра в каком прядкие обратывает dfs
- if (!used[now])
- dfs(now);
- }
- ans.push_back(cur); // добавление вершины в ответ
- }
- void topological_sort() {
- for(int i = 0; i < n; ++i) // проходим по всем вершинам и вызаваем dfs, чтобы обойти все компоненты связности
- if(!used[i])
- dfs(i);
- reverse(ans.begin(), ans.end()); // разворачиваем массив ответа
- }
- int main() {
- int m;
- cin >> n >> m; // считываем граф в качестве списка ребер и преобразуем в список смежности
- for(int i = 0; i < m; ++i){ // алгоритм работает только со списком смежности, так что нужно в любом случае в него преобразовать
- int x, y;
- cin >> x >> y;
- g[x - 1].push_back(y - 1);
- }
- /*cout << '\n'; // если нужно увидеть список смежности
- for(int i = 0; i < n; ++i){
- for(int j = 0; j < g[i].size(); ++j)
- cout << g[i][j] + 1 << " ";
- cout << '\n';
- }
- cout << '\n';*/
- topological_sort(); // собственно вызов функции сортировки и вывод ответа
- for(int i = 0; i < ans.size(); ++i){
- cout << ans[i] + 1 << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement