round_trip_1669.cpp (850B)
1 #include <iostream> 2 #include <vector> 3 4 std::vector<int> cyc; 5 6 int dfs(const std::vector<std::vector<int>>& a, 7 std::vector<bool>& v, int i, int p) { 8 v[i] = true; 9 for (auto x : a.at(i)) { 10 if (x == p) continue; 11 if (v.at(x)) { 12 cyc.push_back(x); 13 cyc.push_back(i); 14 return x; 15 } 16 if (int r = dfs(a, v, x, i); r != 0) { 17 cyc.push_back(i); 18 if (r == i) { 19 std::cout << cyc.size() << "\n"; 20 for (auto y : cyc) std::cout << y << " "; 21 std::cout << "\n"; 22 exit(0); 23 } else return r; 24 } 25 } 26 return 0; 27 } 28 29 int main() { 30 int n, m; 31 std::cin >> n >> m; 32 std::vector<std::vector<int>> a(n+1); 33 for (int i = 0; i < m; i++) { 34 int x, y; 35 std::cin >> x >> y; 36 a[x].push_back(y); 37 a[y].push_back(x); 38 } 39 std::vector<bool> v(n+1); 40 for (int i = 1; i <= n; i++) 41 if (!v.at(i)) 42 dfs(a, v, i, 0); 43 std::cout << "IMPOSSIBLE\n"; 44 }