Тяжёлые и лёгкие вершины

Сумма степеней равна 2m, поэтому вершин со степенью больше корня — меньше корня. Отсюда треугольники за m корень из m.

3 мин

Корень берут не только от длины массива. В графах его берут от степеней вершин, и работает это на одном наблюдении.

Наблюдение

Сумма степеней всех вершин равна $2m$ . Значит, вершин со степенью больше $\sqrt{2m}$ не может быть больше $\sqrt{2m}$ - иначе сумма степеней превысила бы $2m$ .

Назовём такие вершины тяжёлыми, остальные лёгкими. Получаются два утверждения противоположной природы:

лёгкую вершину можно перебрать целиком - это $O(\sqrt m)$ ;
тяжёлых мало, поэтому про них можно позволить себе предподсчёт.

Дальше остаётся разобрать случаи и убедиться, что ни в одном не осталось дорогой ветки.

Ориентация рёбер по степени

Есть вариант того же приёма, в котором делить вершины на два сорта не приходится. Направим каждое ребро от вершины меньшей степени к вершине большей, а при равных степенях - от меньшего номера к большему.

Тогда исходящая степень любой вершины не больше $\sqrt{2m}$ . Доказательство в одну строчку: если у $v$ исходящая степень $k$ , то все $k$ её целей имеют степень не меньше $\deg v \ge k$ , значит сумма степеней не меньше $k^2$ , а она равна $2m$ .

Сравнение по паре «степень, потом номер» задаёт строгий порядок, поэтому циклов в ориентированном графе не возникает.

Треугольники за $O(m\sqrt m)$

После ориентации каждый треугольник становится путём $u \to v \to w$ с ребром $u \to w$ и находится ровно один раз: у трёх вершин треугольника есть единственная наименьшая по этому порядку.

for (int u = 0; u < n; u++) {
    for (int v : outgoing[u]) mark[v] = 1;
    for (int v : outgoing[u])
        for (int w : outgoing[v]) if (mark[w]) triangles++;
    for (int v : outgoing[u]) mark[v] = 0;   // тем же списком, не memset
}

Внутренний перебор стоит

\sum_u \sum_{v \in out(u)} |out(v)| \ \le \ \sqrt{2m} \sum_u |out(u)| \ = \ O(m\sqrt m).

Очистка пометок тем же списком, которым их ставили, - не мелочь. memset на весь массив внутри цикла по вершинам превращает $O(m\sqrt m)$ в $O(n^2)$ , и это самая частая ошибка в этой задаче.

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

Прибавление соседям

Классическая задача: «прибавить $x$ всем соседям вершины $v$ » и «узнать число в вершине $v$ ». В лоб прибавление стоит $\deg v$ , и вершина с миллионом соседей всё ломает.

операция	лёгкая вершина	тяжёлая вершина
прибавить соседям	честно, $O(\sqrt m)$	запомнить: `pending[v] += x`
узнать значение $v$	$own[v]$ плюс сумма `pending` по тяжёлым соседям	то же самое

У любой вершины тяжёлых соседей не больше $\sqrt{2m}$ , поэтому обе операции стоят $O(\sqrt m)$ .

Общие соседи

Запрос «сколько общих друзей у $u$ и $v$ » разбирается по трём случаям:

обе лёгкие - слияние двух отсортированных списков, $O(\sqrt m)$ ;
одна тяжёлая - проход по списку лёгкой с проверкой пометки, $O(\sqrt m)$ ;
обе тяжёлые - ответ берётся из таблицы, посчитанной заранее.

Таблица считается одним проходом: для каждой вершины $w$ перебираются пары тяжёлых среди её друзей, и каждая такая пара получает от $w$ единицу. Стоит это $\sum_w |\{\text{тяжёлые друзья } w\}|^2 \le 2m\sqrt{2m}$ .