From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 04_graph_algorithms/building_roads_1666.cpp | 32 +++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 04_graph_algorithms/building_roads_1666.cpp (limited to '04_graph_algorithms/building_roads_1666.cpp') diff --git a/04_graph_algorithms/building_roads_1666.cpp b/04_graph_algorithms/building_roads_1666.cpp new file mode 100644 index 0000000..cf6ac28 --- /dev/null +++ b/04_graph_algorithms/building_roads_1666.cpp @@ -0,0 +1,32 @@ +#include +#include + +void visit(size_t i, const std::vector>& a, + std::vector& c) { + if (c[i]) return; + c[i] = true; + for (auto j : a[i]) + visit(j, a, c); +} + +int main() { + size_t n, m; + std::cin >> n >> m; + std::vector> a(n); + for (size_t i = 0; i < m; i++) { + size_t x, y; + std::cin >> x >> y; + a[x-1].push_back(y-1); + a[y-1].push_back(x-1); + } + + std::vector c(n, false); + std::vector s; + for (size_t i = 0; i < n; i++) { + if (c[i]) continue; + if (i != 0) s.push_back(i); + visit(i, a, c); + } + std::cout << s.size() << "\n"; + for (auto x : s) std::cout << "1 " << x+1 << "\n"; +} -- cgit v1.3