1. Идея

Даны точки на плоскости — дома, в которых живут друзья. Разрешено переходить от одного дома к другому, если у них совпадает x или y координата. Нужно понять, сколько минимально новых дорог надо построить, чтобы из любого дома можно было добраться до любого другого.

Ключевая идея:
если рассматривать каждый дом как вершину графа, а между двумя домами проводить ребро, когда они лежат на одной вертикали или горизонтали, то задача сводится к следующей:

• найти количество связных компонент в этом графе;
• чтобы объединить k компонент в одну, достаточно k - 1 новых дорог.

Значит, ответ равен:

[ \text{количество компонент} - 1 ]

2. Наблюдения

Наблюдение 1

Если два дома имеют одинаковый x или одинаковый y, между ними уже можно пройти напрямую.

Наблюдение 2

Если из дома A можно добраться до B, а из B до C, то A, B, C находятся в одной связной компоненте, даже если A и C напрямую не соединены.

Наблюдение 3

Если граф распадается на несколько компонент связности, то никакими уже существующими переходами их не объединить. Для этого нужны новые дороги.

Наблюдение 4

Чтобы объединить k отдельных компонент в одну, минимально нужно k - 1 соединение:

• соединяем две компоненты — их число уменьшается на 1;
• повторяем, пока не останется одна.

Это стандартный факт про объединение компонент.

3. Алгоритм

Построим граф неявно:

• каждая точка — вершина;
• вершины i и j соединены, если
  • x[i] == x[j], или
  • y[i] == y[j].

Дальше нужно посчитать число связных компонент.

Это можно сделать с помощью DFS или BFS:

1. Считать все точки.
2. Завести массив used, где used[i] = true, если вершина уже посещена.
3. Для каждой вершины:
   • если она ещё не посещена, запускаем из неё DFS/BFS;
   • после этого увеличиваем число компонент на 1.
4. Ответ: components - 1.

Так как по условию n маленькое, можно просто проверять все пары точек.

4. Почему это работает

Докажем корректность.

Рассмотрим граф, где:

• вершины — дома;
• ребро есть между двумя домами тогда и только тогда, когда у них совпадает x или y.

Тогда:

• если две вершины лежат в одной связной компоненте графа, между соответствующими домами уже существует путь по имеющимся дорогам;
• если вершины лежат в разных компонентах, добраться между ними невозможно без добавления новой дороги.

Значит, задача действительно сводится к объединению всех компонент связности в одну.

Пусть компонент k.

• Одной новой дорогой можно соединить не более двух разных компонент, то есть уменьшить число компонент максимум на 1.
• Чтобы из k компонент получить одну, нужно уменьшить их число на k - 1.
• Следовательно, меньше чем k - 1 дорог недостаточно.
• С другой стороны, всегда можно последовательно соединять компоненты по одной, и тогда k - 1 дорог хватит.

Итак, минимальное число новых дорог равно k - 1.

Так как алгоритм точно находит количество связных компонент, он выдаёт правильный ответ.

5. Сложность

Пусть n — число точек.

Мы сравниваем пары точек при обходе, поэтому:

• время работы: O(n^2)
• память: O(n)

Для ограничений задачи этого более чем достаточно.

CPP

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }

    vector<vector<int>> g(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (a[i].first == a[j].first || a[i].second == a[j].second) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    vector<int> used(n, 0);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            ++components;
            queue<int> q;
            q.push(i);
            used[i] = 1;

            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (int to : g[v]) {
                    if (!used[to]) {
                        used[to] = 1;
                        q.push(to);
                    }
                }
            }
        }
    }

    cout << components - 1 << '\n';
    return 0;
}

PYTHON

from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [tuple(map(int, input().split())) for _ in range(n)]

    g = [[] for _ in range(n)]
    for i in range(n):
        xi, yi = a[i]
        for j in range(i + 1, n):
            xj, yj = a[j]
            if xi == xj or yi == yj:
                g[i].append(j)
                g[j].append(i)

    used = [False] * n
    components = 0

    for i in range(n):
        if not used[i]:
            components += 1
            q = deque([i])
            used[i] = True
            while q:
                v = q.popleft()
                for to in g[v]:
                    if not used[to]:
                        used[to] = True
                        q.append(to)

    print(components - 1)

if __name__ == "__main__":
    main()