building_roads_1666.cpp (668B)
1 #include <iostream> 2 #include <vector> 3 4 void visit(size_t i, const std::vector<std::vector<size_t>>& a, 5 std::vector<bool>& c) { 6 if (c[i]) return; 7 c[i] = true; 8 for (auto j : a[i]) 9 visit(j, a, c); 10 } 11 12 int main() { 13 size_t n, m; 14 std::cin >> n >> m; 15 std::vector<std::vector<size_t>> a(n); 16 for (size_t i = 0; i < m; i++) { 17 size_t x, y; 18 std::cin >> x >> y; 19 a[x-1].push_back(y-1); 20 a[y-1].push_back(x-1); 21 } 22 23 std::vector<bool> c(n, false); 24 std::vector<size_t> s; 25 for (size_t i = 0; i < n; i++) { 26 if (c[i]) continue; 27 if (i != 0) s.push_back(i); 28 visit(i, a, c); 29 } 30 std::cout << s.size() << "\n"; 31 for (auto x : s) std::cout << "1 " << x+1 << "\n"; 32 }