Меньшее к большему

Есть набор множеств, их надо постепенно сливать. Слияние делается переносом элементов из одного в другое.

Если переносить как попало, легко получить квадрат: каждый раз переливаем большое в маленькое.

Правило: всегда переносим меньшее в большее. Одна строка if (a.size() < b.size()) swap(a, b);.

Почему получается $O(n \log n)$

Проследим за одним элементом. Он переносится только тогда, когда лежит в меньшем из двух множеств. После переноса размер множества, в котором он находится, хотя бы удваивается.

Удвоиться от единицы до $n$ можно не больше $\log_2 n$ раз. Значит, каждый элемент переносится не больше $\log_2 n$ раз, а всего переносов не больше $n \log_2 n$.

Обратите внимание, за чем именно мы следим. Не за размером слияния и не за числом слияний — за судьбой отдельного элемента. Это типичный ход в амортизированном анализе.

СНМ на векторах

Из этого сразу получается работающая система непересекающихся множеств — без деревьев и сжатия путей.

vector<int> comp(n);                       // номер множества для элемента
vector<vector<int>> members(n);            // элементы каждого множества
for (int i = 0; i < n; i++) { comp[i] = i; members[i] = {i}; }

void unite(int a, int b) {
    a = comp[a]; b = comp[b];
    if (a == b) return;
    if (members[a].size() < members[b].size()) swap(a, b);
    for (int x : members[b]) { comp[x] = a; members[a].push_back(x); }
    members[b].clear();
    members[b].shrink_to_fit();
}

Запрос get здесь стоит честную единицу — это просто чтение из массива, без всякой амортизации. Платим за это в unite.

Измерено на миллионе элементов и миллионе объединений: 1 842 922 переноса, 224 мс — против 27 мс у версии с деревьями. Медленнее, но асимптотика приличная, а код проще и позволяет в любой момент перечислить элементы множества.

Где ещё это нужно

Слияние множеств в поддеревьях. Обходим дерево, для каждой вершины держим множество (например, set цветов в поддереве) и сливаем детские множества в родительское. Наивно это квадрат, с правилом — $O(n \log^2 n)$ (логарифм от переносов, логарифм от set).

Приём известен как «small to large» и решает целый класс задач вида «для каждой вершины ответьте что-нибудь про её поддерево».

Алгоритм Тарьяна сливает мешки посещённых вершин ровно так же.

Слияние куч и деревьев поиска. Если структура умеет только вставку по одному, сливаем меньшую в большую — и получаем ту же оценку.

Осторожно с «меньшим»

Оценка держится на том, что размер действительно удваивается. Если сравнивать не размеры, а что-то другое — глубину, вес, номер, — рассуждение рушится.

Та же ловушка, что в СНМ с эвристикой по глубине вместо размера: при подвешивании размеры складываются, а глубины нет.