DSU

  1. Постановка задачи (join, get)
  2. Пример использования (для каждой пары вершин [a,b] найти путь: max вес на пути минимален)
  3. Решение списками: join суммарно за O(nlogn), get за O(1)
  4. Решение деревьями
    1. join за O(1), get за длину пути
    2. Эвристика "меньшее к большему". Варианты с ранками и размерами. Доказательство O(logn) для get.
    3. Эвристика сжатия путей. Доказательство O(logn) для этой эвристики (смотрим на количество тяжёлых рёбер).
  5. Доказательство O(log*n) для одновременного применения эвристик
    1. Ранг вершины сперва 0, затем растёт, затем
    2. Ранги по пути вверх растут
    3. Определяем крутые рёбра, считаем их число
    4. Считаем число не крутых рёбер
--- Перерыв ---
  1. Улучшаем рассуждение про O(mlog*n + n)
    1. До O(m + nlog*n)
    2. До O((m+n)log(log*n))
  2. Доказательство c обратной функцией Аккерамана
    1. Вводим прямую функцию Аккермана, оцениваем A1, A2, A3
    2. Вводим прямую обратную Аккермана
    3. Вводим потенциал для оценки СНМ (level, iter)