#include using namespace std; typedef long long ll; typedef pair pii; typedef vector vi; #define sz(x) ((ll)(x).size()) #define all(x) begin(x), end(x) #define rep(i, a, b) for(int i = a; i < (b); ++i) struct Boar { int x, y; bool operator<(const Boar &rhs) const { return std::tie(x, y) < std::tie(rhs.x, rhs.y); } bool operator>(const Boar &rhs) const { return rhs < *this; } bool operator<=(const Boar &rhs) const { return !(rhs < *this); } bool operator>=(const Boar &rhs) const { return !(*this < rhs); } bool operator==(const Boar &rhs) const { return std::tie(x, y) == std::tie(rhs.x, rhs.y); } bool operator!=(const Boar &rhs) const { return !(rhs == *this); } }; #define SUCCESSFUL 1 typedef ll CompId; struct UnionFind { vi e; explicit UnionFind (int n) : e(n, -1){} // int size(int x) {return -e[find(x)];} CompId find(int x) {return e[x] < 0 ? x : find(e[x]);} bool join(CompId a, CompId b) { a = find(a); b = find(b); if (a == b) return false; if (e[a] > e[b]) { std::swap(a, b); } e[a] += e[b]; e[b] = a; return true; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin.exceptions(ios::failbit); int n; cin >> n; vector boars; vector ids; ids.reserve(n); UnionFind union_find(n); ll components_cnt = n; map by_x; map by_y; for (int i = 0; i < n; ++i) { boars.emplace_back(); cin >> boars.back().x >> boars.back().y; Boar& b = boars.back(); CompId comp_id; { auto it_x = by_x.find(b.x); if (it_x == by_x.end()) { by_x[b.x] = i; comp_id = i; } else { assert(union_find.join(i, it_x->second)); --components_cnt; comp_id = it_x->second; } } { auto it_y = by_y.find(b.y); if (it_y == by_y.end()) { by_y[b.y] = comp_id; } else { if (union_find.join(comp_id, it_y->second)) { --components_cnt; } } } } cout << components_cnt - 1 << '\n'; } /* int n; cin >> n; // vector boars; // boars.reserve(n); // set non_visited; vector ids; ids.reserve(n); ll id_cnt = 0; ll components_cnt = 0; map by_x; map by_y; for (int i = 0; i < n; ++i) { // boars.emplace_back(); // cin >> boars.back().x >> boars.back().y; // // by_x[boars.back().x].emplace_back(i); // by_y[boars.back().y].emplace_back(i); // // non_visited.emplace(i); ll x, y; cin >> x >> y; auto by_x_pos = by_x.find(x); auto by_y_pos = by_y.find(y); if (by_x_pos != by_x.end()) { if (by_y_pos != by_y.end()) { if (*((*by_x_pos).second) != *((*by_y_pos).second)) { *((*by_y_pos).second) = *((*by_x_pos).second); components_cnt--; } } else { by_y[y] = ((*by_x_pos).second); } } else if (by_y_pos != by_y.end()) { by_x[x] = ((*by_y_pos).second); } else { components_cnt++; ids.push_back(id_cnt++); by_x[x] = &ids.back(); by_y[y] = &ids.back(); } } cout << components_cnt - 1 << '\n'; */