fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int INF = 1e9;
  9. const ll LINF = 1e18;
  10.  
  11. const int N = 1e5 + 5;
  12.  
  13. // Để kiểm tra một đồ thị vô hướng có tồn tại chu trình hay không
  14. // thì ta kiểm tra có tồn tại cạnh ngược trong cây dfs hay không
  15. int n, m;
  16. vector<int> adj[N];
  17.  
  18. bool vis[N];
  19. int p[N]; // p[u] là đỉnh cha của u trên cây dfs
  20. int cycle_start, cycle_end;
  21.  
  22. void dfs(int u) {
  23. vis[u] = true;
  24. for (int v : adj[u]) {
  25. if (v == p[u]) continue;
  26. if (!vis[v]) {
  27. // (u, v) là cạnh của cây dfs (cạnh nét liền)
  28. p[v] = u;
  29. dfs(v);
  30. }
  31. else {
  32. // (u, v) là cạnh ngược (cạnh nét đứt)
  33. if (cycle_start == -1) {
  34. cycle_start = v;
  35. cycle_end = u;
  36. }
  37. }
  38. }
  39. }
  40.  
  41. int main() {
  42. ios::sync_with_stdio(false);
  43. cin.tie(nullptr);
  44. cin >> n >> m;
  45.  
  46. for (int i = 0; i < m; i++) {
  47. int u, v;
  48. cin >> u >> v;
  49. adj[u].push_back(v);
  50. adj[v].push_back(u);
  51. }
  52.  
  53. cycle_start = -1;
  54. for (int u = 1; u <= n; u++) {
  55. if (!vis[u]) dfs(u);
  56. }
  57.  
  58. if (cycle_start == -1) {
  59. cout << "IMPOSSIBLE";
  60. }
  61. else {
  62. vector<int> cycle;
  63. int t = cycle_end;
  64. while (true) {
  65. cycle.push_back(t);
  66. if (t == cycle_start) break;
  67. t = p[t];
  68. }
  69. reverse(cycle.begin(), cycle.end());
  70. cycle.push_back(cycle_start);
  71.  
  72. cout << cycle.size() << '\n';
  73. for (int u : cycle) cout << u << ' ';
  74. }
  75. }
Success #stdin #stdout 0.01s 6036KB
stdin
5 6
1 3
1 2
5 3
1 5
2 4
4 5
stdout
4
1 3 5 1