fork download
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector<int> ans;
  6. void DFS(int cur, int par, vector<int> &vis, vector<vector<int>> &adjList) {
  7. if(vis[cur] == 1) return;
  8. if(vis[cur] == 2) {
  9. ans.push_back(cur);
  10. return;
  11. }
  12. vis[cur] = 2;
  13. for(auto &nx: adjList[cur]) {
  14. if(nx != par) {
  15. DFS(nx, cur, vis, adjList);
  16. if(ans.size() > 0) {
  17. if(cur == ans.front()) ans.push_back(-1);
  18. else if(ans.back() == nx) ans.push_back(cur);
  19. return;
  20. }
  21. }
  22. }
  23. vis[cur] = 1;
  24. return;
  25. }
  26. int main() {
  27. cin.tie(0);
  28. ios_base::sync_with_stdio(0);
  29. int n, m;
  30. cin >> n >> m;
  31. vector<vector<int>> adjList(n);
  32. vector<int> vis(n);
  33. for(int i = 0; i < m; i++) {
  34. int u, v;
  35. cin >> u >> v;
  36. u--, v--;
  37. adjList[u].push_back(v);
  38. adjList[v].push_back(u);
  39. }
  40.  
  41. for(int i = 0; i < n; i++){
  42. if(!vis[i]){
  43. DFS(i, -1, vis, adjList);
  44. if(!ans.empty()) break;
  45. }
  46. }
  47. if(ans.empty()) {
  48. cout << "IMPOSSIBLE\n";
  49. } else {
  50. cout << ans.size() << '\n';
  51. ans.back() = ans.front();
  52. for(auto a: ans) {
  53. cout << a + 1 << ' ';
  54. }
  55. cout << '\n';
  56. }
  57. return 0;
  58. }
Success #stdin #stdout 0s 5320KB
stdin
10 20
9 8
9 5
6 4
5 10
7 5
7 8
3 4
6 5
2 1
10 4
6 1
9 7
7 3
4 5
2 9
5 3
2 3
8 5
6 7
3 8
stdout
5
9 5 7 8 9