#include #include #include #include #include #include #include std::vector> get_adj_list(const std::unordered_map>& map_x, const std::unordered_map>& map_y, size_t nodes){ std::vector> adjacency_list(nodes); for (auto it : map_x) { for (auto el : it.second) { adjacency_list[el].insert(adjacency_list[el].end(), it.second.begin(), it.second.end()); } } for (auto it : map_y){ for (auto el : it.second) { adjacency_list[el].insert(adjacency_list[el].end(), it.second.begin(), it.second.end()); } } 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::unordered_map>& map_x, const std::unordered_map>& map_y, size_t nodes) { auto adj_list = get_adj_list(map_x, map_y, nodes); 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); for (long long int i = 0; i < nodes; ++i) { std::cin >> node_x >> node_y; auto [itx, insertedx] = map_x.try_emplace(node_x, std::vector()); auto [ity, insertedy] = map_y.try_emplace(node_y, std::vector()); itx->second.push_back(i); ity->second.push_back(i); } std::cout << num_of_moves(map_x, map_y, nodes); return 0; }