Advertisement
meriellez

Untitled

May 22nd, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int n, m; // число вершин
  7. vector<int> g[101]; // граф
  8. bool used[101], r = false;
  9. vector<int> ans, cl;
  10.  
  11. bool dfs (int v) {
  12. if(cl[v] == 1){ return true; }
  13. if(cl[v] == 2){ return false; }
  14. cl[v] = 1;
  15. used[v] = true;
  16. for (size_t i=0; i<g[v].size(); ++i) {
  17. int to = g[v][i];
  18. // cout <<to <<' ';
  19. if (dfs(to)){
  20. return true;
  21. }
  22. }
  23. ans.push_back (v);
  24. cl[v] = 2;
  25. return false;
  26. }
  27.  
  28. /*bool dfs (int v, int s) {
  29. cl[v] = 1;
  30. for (size_t i = 0; i < g[v].size(); i++) {
  31. int to = g[v][i];
  32. if (cl[to] == 0 && to != v && to != s) {
  33. if (dfs (to, v)) return true;
  34. }
  35. else if (cl[to] == 1 && to != v && to != s) {
  36. return true;
  37. }
  38. }
  39. ans.push_back(v);
  40. cl[v] = 2;
  41. return false;
  42. }*/
  43.  
  44. void topological_sort() {
  45. for (int i=0; i<n; ++i)
  46. used[i] = false;
  47. ans.clear();
  48. for (int i=0; i<n; ++i)
  49. if (!used[i]){
  50. //cout <<i <<' ';
  51. if(dfs(i)){
  52. r = true;
  53. }
  54. }
  55. reverse (ans.begin(), ans.end());
  56. if(!r){
  57. cout <<"Yes" <<endl;
  58. for(int i = 0; i < n; i++){
  59. cout <<ans[i] + 1 <<' ';
  60. }
  61. } else {
  62. cout <<"No";
  63. }
  64. /*if (!used[0])
  65. dfs (0);
  66. bool t = true;
  67. for(int i = 0; i < n; i++){
  68. if(!used[i]){cout <<i <<endl; t = false;}
  69. }
  70. if(t){
  71. cout <<"Yes" <<endl;
  72. reverse (ans.begin(), ans.end());
  73. for(int i = 0; i < n; i++){
  74. cout <<ans[i] <<' ';
  75. }
  76. } else {
  77. cout <<"No";
  78. }*/
  79. }
  80.  
  81. int main(){
  82. cin >>n >>m;
  83. cl.assign(n, 0);
  84. for(int i = 0; i < m; i++){
  85. int x, y;
  86. cin >>x >>y;
  87. x--;
  88. y--;
  89. g[x].push_back(y);
  90. //cout <<g[x] <<' ' <<g[y] <<endl;
  91. }
  92. topological_sort();
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement