Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define X first
  4. #define Y second
  5.  
  6. using namespace std;
  7.  
  8. vector<set<int> > gr;
  9. int n, m;
  10. vector<int> p;
  11. vector<int> was;
  12. void find_path(int v, int t){
  13. vector<int> ans;
  14. cout << "Cycle:\n";
  15. while(p[t] != -1){
  16. ans.push_back(t);
  17. t = p[t];
  18. }
  19. ans.push_back(v);
  20. reverse(ans.begin(), ans.end());
  21. for(auto x: ans){
  22. cout << x << ' ';
  23. }
  24. exit(0);
  25.  
  26. }
  27. int dfs(int t, int start){
  28. for(int j : gr[t]){
  29. if(j == start){
  30. return t;
  31. }
  32. if(!was[j]){
  33. was[j] = 1;
  34. p[j] = t;
  35. int k = dfs(j, start);
  36. if(k != -1) return k;
  37. }
  38. }
  39. return -1;
  40. }
  41. int main() {
  42. cin >> n >> m;
  43. gr.resize(n);
  44.  
  45. for(int i = 0;i < m;i++){
  46. int x, y;
  47. cin >> x >> y;
  48. gr[x].insert(y);
  49. }
  50. p.resize(n);
  51. was.resize(n);
  52. for(int i = 0;i < n;i++){
  53. for(int j = 0;j < n;j++) p[j] = -1;
  54. for(int j = 0;j < n;j++) was[j] = 0;
  55. was[i] = 1;
  56. int to = dfs(i, i);
  57. if(to != -1) find_path(i, to);
  58. }
  59. cout << "No cycles";
  60. return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement