Guest User

Untitled

a guest
Feb 18th, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <string.h>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <set>
  6. #include <iomanip>
  7. #include <limits.h>
  8. #include <functional>
  9. #include <string>
  10. #include <vector>
  11. #include <tuple>
  12. #include <stack>
  13.  
  14. using namespace std;
  15.  
  16. const int INF = (int) 1e7;
  17.  
  18. int cycle_st = -1, cycle_end = -1;
  19.  
  20. void dfs(vector<vector<int>> &g, vector<int> &color, int v, stack<int> &move) {
  21. color[v] = 1;
  22. move.push(v);
  23. for (int i : g[v]) {
  24. if (color[i] == 1 && i != v) {
  25. cycle_end = v;
  26. cycle_st = i;
  27. }
  28. if (color[i] == 0) {
  29. dfs(g, color, i, move);
  30. }
  31. }
  32. color[v] = 2;
  33. }
  34.  
  35. int main() {
  36. int n;
  37. cin >> n;
  38. vector<vector<int>> g(n);
  39.  
  40. for (int i = 0; i < n; ++i) {
  41. int a, b;
  42. cin >> a >> b;
  43. --a; --b;
  44. g[a].push_back(b);
  45. g[a].push_back(a);
  46. }
  47. vector<int> color(n);
  48. stack<int> move;
  49. dfs(g, color, 0, move);
  50. bool x = false;
  51. vector<int> cycle;
  52.  
  53. while (!move.empty()) {
  54. if (move.top() == cycle_end)
  55. x = true;
  56.  
  57. if (move.top() == cycle_st)
  58. x = false;
  59.  
  60. if (x) {
  61. cycle.push_back(move.top() + 1);
  62. }
  63. move.pop();
  64. }
  65. cycle.push_back(cycle_st + 1);
  66. reverse(begin(cycle), end(cycle));
  67. cout << cycle.size() << endl;
  68.  
  69. for (int i : cycle)
  70. cout << i << " ";
  71.  
  72. #ifdef DIMA_DEBUG
  73. system("pause");
  74. #endif // DIMA_DEBUG
  75.  
  76. }
Add Comment
Please, Sign In to add comment