fork(13) download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность
  6. color[v] = 1;
  7. for (size_t i = 0; i < graph[v].size(); ++i) {
  8. int to = graph[v][i];
  9. if (color[to] == 0) { //если в вершину не входили ни разу
  10. if (cyclic (to, cycle_st, graph, color)) return true;
  11. }
  12. else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл
  13. cycle_st = to; // и меняем значение индикатора
  14. return true;
  15. }
  16. }
  17. color[v] = 2; //указываем, что в вершину больше ни разу входить не будем
  18. return false;
  19. }
  20. void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
  21. used[v] = true; //указываем, что использовали данную вершину
  22. for (int i=0; i < graph[v].size(); i++) {
  23. int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v
  24. if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё
  25. dfs (to, graph, used, answer);
  26. }
  27. answer.push_back (v+1); // заносим вершину в вектор, хранящий результат
  28. }
  29.  
  30. void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
  31. for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована
  32. used[i] = false;
  33. for (int i = 0; i < n; i++)
  34. if (!used[i]) //если в ходе предыдущий операций вершина не использовалась
  35. dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину
  36. reverse (answer.begin(), answer.end());
  37. }
  38.  
  39. int main() {
  40. int n, m; // число вершин и ребер
  41. cin >> n >> m;
  42. int a, b;
  43. vector <int> graph[100001]; // граф
  44. vector <bool> used (n);
  45. vector<int> answer;
  46. vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.
  47. int cycle_st = -1;
  48. for (int i = 0; i < m; i++){
  49. cin >> a >> b;
  50. graph[a-1].push_back(b-1);
  51. }
  52. for (int i = 0; i < n; i++){
  53. if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность
  54. break;
  55. }
  56. if (cycle_st != -1){
  57. cout << "-1";
  58. }
  59. else{
  60. topological_sort(n, graph, used, answer);
  61. for (int i = 0; i < answer.size(); i++)
  62. {
  63. cout << answer[i] << " ";
  64. }
  65. cout << endl;
  66. }
  67. return 0;
  68. }
Success #stdin #stdout 0s 4508KB
stdin
4 5
1 2
1 3
3 4
2 4
4 1
stdout
-1