#include #include #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::unordered_set bfs(const std::vector>& adjacency_list, int start) { std::unordered_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::unordered_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() { std::ios_base::sync_with_stdio(false); long long int nodes, node_x, node_y; std::cin >> nodes; std::unordered_map map_x; std::unordered_map map_y; //std::vector> node_locations; //node_locations.reserve(nodes); size_t connected_components = 0; for (size_t i = 0; i < nodes; ++i) { std::cin >> node_x >> node_y; auto [itx, insertedx] = map_x.try_emplace(node_x, true); auto [ity, insertedy] = map_y.try_emplace(node_y, true); if (insertedx && insertedy) connected_components++; } //std::cout << num_of_moves(node_locations) std::cout << connected_components - 1; return 0; }