Граф (Розбір)

Лексикографічно найменше топологічне сортування будується алгоритмом Кана з чергою з пріоритетом: на кожному кроці серед усіх доступних вершин (вершин, у які не входить жодне ребро з ще не виписаних вершин) обирається вершина з найменшим номером.

Додане ребро $u \to v$ u \to v робить вершину $v$ недоступною доти, доки не буде виписано вершину $u$ . Отже, додаючи ребра, ми можемо "ховати" малі вершини й тим самим змушувати алгоритм обирати вершини з більшими номерами. Кожна схована вершина коштує одне ребро із запасу $k$ .

Жадібна ідея. Будуватимемо відповідь позиція за позицією. Лексикографічне порівняння визначається першою позицією, на якій послідовності відрізняються, тому на кожній позиції треба поставити вершину з найбільшим можливим номером — жодні виграші на наступних позиціях не компенсують програш на поточній.

Розділимо вершини, які можна виписати на поточному кроці, на дві множини:

$A$ — доступні вершини: усі ребра, що входять у них, уже "зняті". Якщо нічого не робити, алгоритм Кана обере найменшу вершину з $A$ ;
$B$ — відкладені вершини. Це вершини, які були доступними, але ми вирішили їх сховати. Для кожної такої вершини ми зобов'язуємося додати ребро, що входить у неї. Початок цього ребра ми оберемо пізніше — ним стане вершина, виписана безпосередньо перед відкладеною.

Множину $A$ зберігаємо в черзі з пріоритетом з найменшим елементом на вершині (min-купа), а множину $B$ — у черзі з пріоритетом з найбільшим елементом на вершині (max-купа).

Коли вигідно відкладати вершину. Нехай $x$ — найменша вершина в $A$ . Якщо її не чіпати, на поточну позицію стане $x$ . Відкладати $x$ (витрачати ребро) має сенс у двох випадках:

в $A$ є щонайменше дві вершини. Тоді після того, як $x$ буде відкладено, на поточну позицію стане наступна за зростанням вершина з $A$ , яка більша за $x$ ;
в $A$ є лише вершина $x$ , але в $B$ є відкладена вершина $y > x$ y > x. Тоді після відкладання $x$ множина $A$ стане порожньою, і на поточну позицію стане найбільша відкладена вершина — число, більше за $x$ .

В усіх інших випадках відкладання не збільшує число на поточній позиції, і витрачати ребро не потрібно. Відкладаємо вершини по одній, починаючи з найменшої, доки це вигідно і доки не вичерпано запас $k$ .

Яку вершину виписати. Після відкладання:

якщо $A$ не порожня, виписуємо найменшу вершину з $A$ — цього вимагає правило лексикографічно найменшого сортування;
якщо $A$ порожня, виписуємо найбільшу відкладену вершину $v$ з $B$ і додаємо ребро з останньої виписаної вершини у $v$ . Саме це ребро "ховало" вершину $v$ : досі вона була недоступною, а тепер, коли виписано її нового попередника, вона стає єдиною доступною вершиною. Решта відкладених вершин лишаються схованими — їхні ребра буде додано пізніше.

Потім, як зазвичай в алгоритмі Кана, зменшуємо вхідні степені сусідів виписаної вершини; вершини, вхідний степінь яких стає нульовим, додаються до $A$ .

Чому відповідь коректна. Кожну відкладену вершину рано чи пізно буде виписано з $B$ , і саме в цей момент додається рівно одне ребро. Тому кількість доданих ребер дорівнює кількості відкладань і не перевищує $k$ . Усі додані ребра йдуть з вершини, виписаної раніше, у вершину, виписану пізніше, тому знайдений порядок є топологічним сортуванням нового графа, і циклів не виникає.

Складність. Кожна вершина потрапляє до $A$ не більше одного разу і до $B$ не більше одного разу, а кожне ребро графа переглядається один раз. Загальна складність становить $O ((n + m) lo g n)$ O((n + m) \log n).

Алгоритм розв'язання задачі

Використовуємо алгоритм Кана і дві черги з пріоритетом:

$A$ — min-купа, що зберігає доступні вершини; на її вершині — вершина з найменшим номером.
$B$ — max-купа, що зберігає відкладені вершини; на її вершині — вершина з найбільшим номером.

Оголосимо такі масиви:

$in d e g [v]$ indeg[v] — кількість вхідних ребер вершини $v$ , які ще не оброблено;
$an s$ — результуюче топологічне впорядкування;
$e d g es$ — список доданих ребер.

Крок 1. Ініціалізація

Обчислити вхідний степінь кожної вершини.
Додати до $A$ усі вершини з нульовим вхідним степенем.
Ініціалізувати $B$ і список $e d g es$ порожніми.

Крок 2. Побудова відповіді

Доки не оброблено всі $n$ вершин:

1. Відкласти вершину, якщо це вигідно.

Доки кількість доданих ребер менша за $k$ , купа $A$ не порожня і виконується хоча б одна з умов:

$A$ містить щонайменше дві вершини;
$A$ містить одну вершину $x$ , а $B$ містить вершину $y$ таку, що $y > x$ y > x.

Вилучити найменшу вершину $x$ з $A$ і додати її до $B$ . Цю вершину буде оброблено пізніше.

2. Обрати наступну вершину.

Якщо $A$ не порожня, вилучити з неї найменшу вершину $v$ .
Інакше вилучити найбільшу вершину $v$ з $B$ . Якщо $an s$ не порожній, додати ребро з останньої вершини в $an s$ у $v$ .

Додати $v$ у кінець $an s$ .

3. Оновити граф.

Для кожного вихідного ребра $v \to u$ v \to u:

Зменшити $in d e g [u]$ indeg[u] на одиницю.
Якщо $in d e g [u]$ indeg[u] став рівним нулю, додати $u$ до $A$ .

Повторювати ці кроки, доки всі вершини не потраплять до $an s$ .

Крок 3. Виведення

Вивести послідовність $an s$ .
Вивести кількість доданих ребер.
Вивести самі додані ребра.

Приклад

Розглянемо приклад з умови: $n = 5$ n = 5, $k = 2$ k = 2, ребра $1 \to 4$ 1 \to 4, $4 \to 2$ 4 \to 2, $1 \to 3$ 1 \to 3. Початкові вхідні степені: вершини $1$ і $5$ мають вхідний степінь $0$ , вершини $2, 3, 4$ — вхідний степінь $1$ . Початкові множини: $A = {1, 5}$ A = \{1, 5\}, $B = {}$ B = \{\,\}.

Крок	Відкладаємо	$A$	$B$	$k$	Беремо	Ребро	Порядок
$1$	$1$ (в $A$ дві вершини)	${5}$	${1}$	$1$	$5$ з $A$	—	$5$
$2$	—	${}$	${1}$	$1$	$1$ з $B$	$5 \to 1$ 5 \to 1	$5, 1$
$3$	$3$ (в $A$ дві вершини: $3$ і $4$ )	${4}$	${3}$	$0$	$4$ з $A$	—	$5, 1, 4$
$4$	— ( $k = 0$ k = 0)	${2}$	${3}$	$0$	$2$ з $A$	—	$5, 1, 4, 2$ 5, 1, 4, 2
$5$	—	${}$	${3}$	$0$	$3$ з $B$	$2 \to 3$ 2 \to 3	$5, 1, 4, 2, 3$ 5, 1, 4, 2, 3

Розглянемо кроки докладніше.

Крок 1. $A = {1, 5}$ A = \{1, 5\} містить дві вершини, тому відкладаємо найменшу — $1$ . Тепер $A = {5}$ A = \{5\} містить одну вершину, а в $B$ немає вершин, більших за $5$ , тому припиняємо відкладання. Виписуємо $5$ .
Крок 2. $A$ порожня. Виписуємо найбільшу відкладену вершину $1$ і додаємо ребро $5 \to 1$ 5 \to 1. Знімаємо ребра $1 \to 4$ 1 \to 4 і $1 \to 3$ 1 \to 3: вершини $4$ і $3$ стають доступними, $A = {3, 4}$ A = \{3, 4\}.
Крок 3. $A$ містить дві вершини — відкладаємо $3$ , і запас ребер вичерпано ( $k = 0$ k = 0). Виписуємо $4$ , після чого ребро $4 \to 2$ 4 \to 2 знімається і $A = {2}$ A = \{2\}.
Крок 4. Відкладати більше неможливо. Виписуємо $2$ .
Крок 5. $A$ порожня. Виписуємо відкладену вершину $3$ і додаємо ребро $2 \to 3$ 2 \to 3.

Отримуємо порядок $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 і додані ребра $5 \to 1$ 5 \to 1 та $2 \to 3$ 2 \to 3. Початковий граф (ліворуч) і граф з доданими ребрами (праворуч, додані ребра позначено червоним):

Без доданих ребер лексикографічно найменше сортування таке: $1, 3, 4, 2, 5$ 1, 3, 4, 2, 5: вершина $5$ ні з чим не пов'язана, але через великий номер обирається останньою. Після додавання двох ребер вершина $5$ стає першою, і порядок $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 лексикографічно більший.

Розглянемо ще один приклад, у якому на початку доступні чотири вершини. Нехай $n = 8, m = 6, k = 4$ n = 8, m = 6, k = 4, а ребра графа такі: $6 \to 3, 4 \to 8, 3 \to 5, 1 \to 7, 2 \to 7, 5 \to 7$ 6 \to 3, 4 \to 8, 3 \to 5, 1 \to 7, 2 \to 7, 5 \to 7.

У вершини $1, 2, 4, 6$ 1, 2, 4, 6 не входить жодне ребро, тому на початку $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $B = {}$ B = \{\,\}. Без доданих ребер лексикографічно найменше сортування таке: $1, 2, 4, 6, 3, 5, 7, 8$ 1, 2, 4, 6, 3, 5, 7, 8.

Початковий граф (ліворуч) і граф після додавання ребер (праворуч, додані ребра позначено червоним)

Крок	$A$ до	$B$ до	$k$	Відкладаємо	Беремо	Ребро
$1$	${1, 2, 4, 6}$ \{1, 2, 4, 6\}	${}$	$4$	$1, 2, 4$	$6$ з $A$	—
$2$	${3}$	${4, 2, 1}$ \{4, 2, 1\}	$1$	$3 (4 > 3)$ 3~(4 > 3)	$4$ з $B$	$6 \to 4$ 6 \to 4
$3$	${8}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$8$ з $A$	—
$4$	${}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$3$ з $B$	$8 \to 3$ 8 \to 3
$5$	${5}$	${2, 1}$	$0$	—	$5$ з $A$	—
$6$	${}$	${2, 1}$	$0$	—	$2$ з $B$	$5 \to 2$ 5 \to 2
$7$	${}$	${1}$	$0$	—	$1$ з $B$	$2 \to 1$ 2 \to 1
$8$	${7}$	${}$	$0$	—	$7$ з $A$	—

Розглянемо кроки докладніше.

Крок 1. $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $k = 4$ k = 4. Відкладаємо вершину $1$ , оскільки $A$ містить чотири вершини, потім $2$ (в $A$ три вершини), потім $4$ (в $A$ дві вершини). Запас зменшується до $k = 1$ k = 1. Тепер $A = {6}$ A = \{6\} містить одну вершину, а найбільша відкладена вершина $4$ менша за $6$ — подальше відкладання невигідне. Виписуємо $6$ . Ребро $6 \to 3$ 6 \to 3 знімається, і $A = {3}$ A = \{3\}.
Крок 2. $A = {3}$ A = \{3\}, $B = {4, 2, 1}$ B = \{4, 2, 1\}, $k = 1$ k = 1. $A$ містить одну вершину, але $B$ містить вершину $4 > 3$ 4 > 3, тому відкладаємо і $3$ ; запас вичерпано, $k = 0$ k = 0. $A$ порожня — виписуємо найбільшу відкладену вершину $4$ і додаємо ребро $6 \to 4$ 6 \to 4. Ребро $4 \to 8$ 4 \to 8 знімається, і $A = {8}$ A = \{8\}.
Крок 3. Відкладати більше неможливо. Виписуємо $8$ , після чого $A$ порожня.
Крок 4. Виписуємо найбільшу відкладену вершину $3$ і додаємо ребро $8 \to 3$ 8 \to 3. Ребро $3 \to 5$ 3 \to 5 знімається, і $A = {5}$ A = \{5\}.
Крок 5. Виписуємо $5$ . Ребро $5 \to 7$ 5 \to 7 знімається, але у вершину $7$ ще входять ребра з $1$ і $2$ , тому $A$ порожня.
Крок 6. Виписуємо відкладену вершину $2$ і додаємо ребро $5 \to 2$ 5 \to 2. Ребро $2 \to 7$ 2 \to 7 знімається.
Крок 7. Виписуємо відкладену вершину $1$ і додаємо ребро $2 \to 1$ 2 \to 1. Ребро $1 \to 7$ 1 \to 7 знімається, і $A = {7}$ A = \{7\}.
Крок 8. Виписуємо $7$ .

Відповідь:

6 4 8 3 5 2 1 7
4
6 4
8 3
5 2
2 1

Цей приклад добре ілюструє всі випадки роботи алгоритму. На кроці $1$ відкладаються одразу три вершини — доки $A$ містить щонайменше дві вершини. На кроці $2$ спрацьовує друга умова: $A$ містить лише вершину $3$ , але $B$ містить більшу вершину $4$ , тому $3$ теж відкладається. Відкладені вершини залишають $B$ у порядку спадання $(4, 3, 2, 1)$ (4, 3, 2, 1), і кожна з них отримує рівно одне ребро з вершини, виписаної перед нею. Тому ребер додано рівно стільки, скільки було відкладань, — чотири.

Реалізація алгоритму

Читаємо вхідні дані. Будуємо граф. Списки суміжності зберігаємо в $g$ , вхідні степені — в $in d e g$ .

scanf("%d %d %d", &n, &m, &k);
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  indeg[v]++;
}

C++

Оголосимо дві черги з пріоритетом: $A$ — доступні вершини, з найменшим елементом на вершині (min-купа); $B$ — відкладені вершини, з найбільшим елементом на вершині (max-купа).

priority_queue<int, vector<int>, greater<int>> A; // доступні, min-купа
priority_queue<int> B;                            // відкладені, max-купа

Спочатку доступні всі вершини з нульовим вхідним степенем.

for (int v = 1; v <= n; v++)
  if (indeg[v] == 0) A.push(v);

У масиві $or d er$ накопичуємо відповідь — шукане топологічне сортування, а в масиві $a dd e d$ зберігаємо додані ребра.

vector<int> order;
order.reserve(n);
vector<pair<int, int>> added;

Кожна ітерація циклу додає до відповіді одну вершину, доки не буде виписано всі $n$ вершин.

while ((int)order.size() < n)
{

Відкладаємо вершини. Доки в запасі залишаються ребра і множина $A$ не порожня, розглядаємо найменшу доступну вершину $x$ . Її вигідно відкласти, якщо $A$ містить ще хоча б одну вершину або якщо $B$ містить відкладену вершину з більшим номером. Відкладена вершина переноситься з $A$ до $B$ , а запас $k$ зменшується на $1$ . Інакше відкладання припиняється.

  // відкладаємо вершини, доки це вигідно і є запас ребер
  while (k > 0 && !A.empty())
  {
    int x = A.top();
    if (A.size() >= 2 || (!B.empty() && B.top() > x))
    {
      A.pop();
      B.push(x);
      k--;
    }
    else break;
  }

C++

Обираємо вершину $v$ , яку буде виписано на поточну позицію. Якщо $A$ не порожня, це найменша доступна вершина. Інакше беремо найбільшу відкладену вершину і додаємо ребро з останньої виписаної вершини $or d er . ba c k ()$ order.back() у $v$ .

  int v;
  if (!A.empty())
  {
    v = A.top();
    A.pop();
  }
  else
  {
    v = B.top();
    B.pop();
    added.push_back(make_pair(order.back(), v));
  }

C++

Дописуємо $v$ до відповіді і, як в алгоритмі Кана, зменшуємо вхідні степені її сусідів. Вершини, вхідний степінь яких став нульовим, стають доступними.

  order.push_back(v);
  for (int to : g[v])
    if (--indeg[to] == 0) A.push(to);
}

Виводимо знайдене топологічне сортування, кількість доданих ребер і самі ребра.

for (int i = 0; i < n; i++)
  printf("%d ", order[i]);
printf("\n%d\n", added.size());
for (auto &e : added)
  printf("%d %d\n", e.first, e.second);