Advertisement
mr1302

Topological sorting on DFS

Oct 30th, 2020
1,729
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None | 0 0
  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 10000; // максимальное количество верщин
  8.  
  9. int n; // число вершин
  10. vector<vector<int>> g(MAXN); // граф
  11. vector<bool> used (MAXN, false); // массив индикации
  12. vector<int> ans; // массив ответа
  13.  
  14. void dfs(int cur) { // почти стандартный dfs, просто добавляем вершины в ответ после их обработки
  15.     used[cur] = true;
  16.     for(auto now : g[cur]){
  17.         //cout << cur + 1 << " " << now + 1 << '\n'; если нужно увидеть какие ребра в каком прядкие обратывает dfs
  18.         if (!used[now])
  19.             dfs(now);
  20.     }
  21.     ans.push_back(cur); // добавление вершины в ответ
  22. }
  23.  
  24. void topological_sort() {
  25.     for(int i = 0; i < n; ++i) // проходим по всем вершинам и вызаваем dfs, чтобы обойти все компоненты связности
  26.         if(!used[i])
  27.             dfs(i);
  28.     reverse(ans.begin(), ans.end()); // разворачиваем массив ответа
  29. }
  30.  
  31. int main() {
  32.     int m;
  33.     cin >> n >> m; // считываем граф в качестве списка ребер и преобразуем в список смежности
  34.     for(int i = 0; i < m; ++i){ // алгоритм работает только со списком смежности, так что нужно в любом случае в него преобразовать
  35.         int x, y;
  36.         cin >> x >> y;
  37.         g[x - 1].push_back(y - 1);
  38.     }
  39.     /*cout << '\n';  // если нужно увидеть список смежности
  40.     for(int i = 0; i < n; ++i){
  41.         for(int j = 0; j < g[i].size(); ++j)
  42.             cout << g[i][j] + 1 << " ";
  43.         cout << '\n';
  44.     }
  45.     cout << '\n';*/
  46.     topological_sort(); // собственно вызов функции сортировки и вывод ответа
  47.     for(int i = 0; i < ans.size(); ++i){
  48.         cout << ans[i] + 1 << " ";
  49.     }
  50.     return 0;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement