L. Порядок кружков

Кружки надо посетить все, соблюдая требования «сначала такие-то». За $i$-й по счёту посещённый кружок с номером $j$ дают $N^{i-1} \cdot j$ конфет. Найдите порядок посещения, дающий наибольшее число конфет.

Разбираемся с весами

Награда - это число $\sum_i N^{i-1} j_i$, то есть запись числа в системе счисления с основанием $N$, где цифра позиции $i$ равна номеру кружка $j_i$.

Старшая позиция - последняя посещённая. Значит максимизировать надо в таком порядке: сначала номер на последнем месте, потом на предпоследнем, и так далее. Цифры не переполняются: номер кружка меньше $N$.

Это не «лексикографически максимальный порядок»: тот максимизирует первую позицию. Правильная формулировка - лексикографически максимальная последовательность, если читать её с конца.

Как это построить

Выбираем последний элемент: им может быть любой кружок, от которого никто не зависит, - в графе требований это вершина с нулевой исходящей степенью. Из них берём наибольший. Убираем и повторяем.

То есть обычный алгоритм Кана, но на обращённом графе и с кучей максимумов; полученную последовательность в конце разворачиваем.

for (int v = 1; v <= n; v++) if (outdeg[v] == 0) ready.push(v);   // max-heap
while (!ready.empty()) {
    int v = ready.top(); ready.pop();
    tail.push_back(v);
    for (int p : prerequisites[v]) if (--outdeg[p] == 0) ready.push(p);
}
std::reverse(tail.begin(), tail.end());

Почему жадность работает

Последняя позиция весит больше, чем все остальные вместе: $N^{N-1} > \sum_{i<N-1} N^i \cdot (N-1)$ при основании $N$. Поэтому увеличить номер на последней позиции всегда выгоднее, чем что угодно на всех предыдущих. Дальше рассуждение повторяется для оставшихся позиций.

Подробнее: «Топологическая сортировка».

В первой строке - число кружков $N$ ($1 \le N \le 10^5$).

В следующих $N$ строках - описание требований: сначала $k_i$ ($0 \le k_i \le N-1$), затем $k_i$ номеров кружков, которые надо пройти до $i$-го. Сумма $k_i$ не превосходит $2 \cdot 10^5$. Порядок, удовлетворяющий всем требованиям, существует.

Выведите $N$ номеров - порядок посещения, дающий наибольшее число конфет.