From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 6 Jul 2026 19:08:08 +0200
Subject: Initial commit

---
 04_graph_algorithms/round_trip_1669.cpp | 44 +++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
 create mode 100644 04_graph_algorithms/round_trip_1669.cpp

(limited to '04_graph_algorithms/round_trip_1669.cpp')

diff --git a/04_graph_algorithms/round_trip_1669.cpp b/04_graph_algorithms/round_trip_1669.cpp
new file mode 100644
index 0000000..c19b29d
--- /dev/null
+++ b/04_graph_algorithms/round_trip_1669.cpp
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <vector>
+
+std::vector<int> cyc;
+
+int dfs(const std::vector<std::vector<int>>& a,
+    std::vector<bool>& v, int i, int p) {
+	v[i] = true;
+	for (auto x : a.at(i)) {
+		if (x == p) continue;
+		if (v.at(x)) {
+			cyc.push_back(x);
+			cyc.push_back(i);
+			return x;
+		}
+		if (int r = dfs(a, v, x, i); r != 0) {
+			cyc.push_back(i);
+			if (r == i) {
+				std::cout << cyc.size() << "\n";
+				for (auto y : cyc) std::cout << y << " ";
+				std::cout << "\n";
+				exit(0);
+			} else return r;
+		}
+	}
+	return 0;
+}
+
+int main() {
+	int n, m;
+	std::cin >> n >> m;
+	std::vector<std::vector<int>> a(n+1);
+	for (int i = 0; i < m; i++) {
+		int x, y;
+		std::cin >> x >> y;
+		a[x].push_back(y);
+		a[y].push_back(x);
+	}
+	std::vector<bool> v(n+1);
+	for (int i = 1; i <= n; i++)
+		if (!v.at(i))
+			dfs(a, v, i, 0);
+	std::cout << "IMPOSSIBLE\n";
+}
-- 
cgit v1.3