#include #include #include #include std::vector> get_adj_list(const std::vector>& node_locations){ std::vector> adjacency_list(node_locations.size()); for (size_t i = 0; i < adjacency_list.size(); ++i) { auto [node_x, node_y] = node_locations[i]; for (size_t j = 0; j < adjacency_list.size(); ++j) { if (j == i) continue; auto [n_node_x, n_node_y] = node_locations[j]; if (n_node_x == node_x) adjacency_list[i].push_back(j); if (n_node_y == node_y) adjacency_list[i].push_back(j); } } return adjacency_list; } std::set bfs(const std::vector>& adjacency_list, int start) { std::set reached_nodes; std::vector reached(adjacency_list.size(), false); std::queue q; q.push(start); while (!q.empty()){ auto node = q.front(); q.pop(); if (!reached[node]){ reached[node] = true; reached_nodes.insert(node); for (auto neighbor : adjacency_list[node]) q.push(neighbor); } } return reached_nodes; } size_t get_num_of_connected_components(const std::vector>& adjacency_list) { size_t ret = 0; std::set reached_nodes; for (size_t i = 0; i < adjacency_list.size(); ++i) { if (reached_nodes.find(i) == reached_nodes.end()){ reached_nodes.merge(bfs(adjacency_list, i)); ret++; } } return ret; } int num_of_moves(const std::vector>& node_locations) { auto adj_list = get_adj_list(node_locations); size_t num_of_connected_components = get_num_of_connected_components(adj_list); return num_of_connected_components - 1; } int main() { size_t nodes, node_x, node_y; std::cin >> nodes; std::vector> node_locations; node_locations.reserve(nodes); for (size_t i = 0; i < nodes; ++i) { std::cin >> node_x >> node_y; node_locations.emplace_back(node_x, node_y); } std::cout << num_of_moves(node_locations); return 0; }