Самотній острів (Розбір)

За умовою задачі, якщо ви залишили острів, повернутися на нього вже неможливо. Отже, граф, вершинами якого є острови, а ребрами — мости, є орієнтованим ациклічним графом. Застрягнути можна лише на острові $v$ , з якого не виходить жоден міст, тобто у тупиковій вершині з нульовим вихідним степенем: $O u t D e g r ee [v] = 0$ OutDegree[v] = 0.

Нехай $p r o b [v]$ prob[v] позначає ймовірність того, що під час прогулянки ми потрапимо у вершину $v$ . Для стартової вершини $p r o b [r] = 1$ prob[r] = 1; для всіх інших вершин спочатку $p r o b [v] = 0$ prob[v] = 0. Оскільки граф не містить циклів, кожну вершину можна відвідати не більше одного разу.

Припустимо, з вершини $u$ виходить $O u t D e g r ee [u]$ OutDegree[u] ребер. Перебуваючи у $u$ , ми обираємо одне з них рівноймовірно, тому переходимо по кожному ребру $u \to v$ u \to v з ймовірністю $p r o b [u] / O u t D e g r ee [u]$ prob[u] / OutDegree[u]. У вершину $v$ можна потрапити лише з її безпосередніх попередників. Тому $p r o b [v]$ prob[v] дорівнює сумі внесків усіх ребер $u \to v$ u \to v, що входять у $v$ :

p r o b [v] = u \to v \sum p r o b [u] / O u t D e g r ee [u]

prob[v] = \sum_{u \to v} prob[u] / OutDegree[u]

Значення $p r o b [v]$ prob[v] можна обчислити лише тоді, коли ймовірності всіх його попередників уже остаточні. Саме такий порядок обробки задає топологічне сортування: кожна вершина з'являється після усіх вершин, з яких у неї ведуть ребра. Тому ми будуємо топологічний порядок за допомогою алгоритму Кана і одночасно "проштовхуємо" ймовірності вздовж ребер.

Алгоритм виглядає так:

для кожної вершини $v$ обчислити її вхідний степінь $I n D e g r ee [v]$ InDegree[v] та вихідний степінь $O u t D e g r ee [v]$ OutDegree[v];
додати до черги всі вершини з нульовим вхідним степенем і встановити $p r o b [r] = 1$ prob[r] = 1;
поки черга не порожня, вилучити з неї вершину $v$ . На цей момент усі її попередники вже оброблені, тож значення $p r o b [v]$ prob[v] остаточне. Для кожного ребра $v \to t o$ v \to to додати $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v] до $p r o b [t o]$ prob[to] і зменшити $I n D e g r ee [t o]$ InDegree[to] на $1$ . Якщо вхідний степінь вершини $t o$ стає нульовим, додати її до черги.

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

Знаходження відповіді. Серед тупикових вершин знайдіть максимальну ймовірність $m x$ . Потім виведіть, у порядку зростання, індекси всіх тупикових вершин $v$ , для яких $∣ p r o b [v] - m x ∣ \leq 1 0^{- 9}$ |prob[v] - mx| \le 10^{-9}. Порівняння з допуском необхідне, оскільки ймовірності обчислюються у числах з плаваючою комою з похибками округлення.

Складність. Кожна вершина додається до черги та вилучається з неї рівно один раз, а кожне ребро розглядається один раз. Час роботи алгоритму становить $O (n + m)$ O(n + m).

Приклад

Змоделюємо роботу алгоритму на графі з прикладу. Поруч із кожною вершиною показано ймовірність $p r o b [v]$ prob[v] потрапляння до неї. Оброблені вершини зафарбовано сірим, ребра, вздовж яких ймовірність розподіляється на поточному кроці, виділено синім, а вже розглянуті ребра зображено пунктиром.

Спочатку (ліва фігура) $p r o b [1] = 1$ prob[1] = 1, а ймовірності всіх інших вершин дорівнюють $0$ . Вершина $1$ — єдина вершина з нульовим вхідним степенем, тому вона першою вилучається з черги.

З вершини $1$ виходить чотири ребра, тому ймовірність $p r o b [1] = 1$ prob[1] = 1 рівномірно розподіляється між вершинами $2, 3, 4$ та $5$ : кожна з них отримує $1/4 = 0.25$ 1 / 4 = 0.25 (права фігура). Після видалення ребер, що виходять з вершини $1$ , вхідні степені вершин $2$ та $3$ стають нульовими, і їх додають до черги.

Далі обробляється вершина $2$ . З неї виходить два ребра, тому до $p r o b [4]$ та $p r o b [5]$ додається $p r o b [2] /2 = 0.25/2 = 0.125$ prob[2] / 2 = 0.25 / 2 = 0.125. Отримуємо $p r o b [4] = p r o b [5] = 0.375$ prob[4] = prob[5] = 0.375 (нижня ліва фігура). Вхідний степінь вершини $5$ стає нульовим, і її додають до черги.

Наступною обробляється вершина $3$ . З неї виходить одне ребро $3 \to 4$ 3 \to 4, тому $p r o b [4]$ збільшується на $p r o b [3] /1 = 0.25$ prob[3] / 1 = 0.25 і стає $0.625$ (нижня права фігура). Тепер вершину $4$ також додають до черги.

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

Тупикові вершини — це $4$ та $5$ , з ймовірностями $0.625$ та $0.375$ відповідно. Їхня сума дорівнює $1$ : ми напевно десь застрягнемо. Максимальна ймовірність досягається у єдиній вершині $4$ , яка і є відповіддю.

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

Оголосимо константу $E P S$ — допуск для порівняння чисел з плаваючою комою.

#define EPS 1e-9

Зберігатимемо вхідний граф у вигляді списку суміжності $g$ . Вхідні та вихідні степені вершин зберігатимемо у масивах $I n D e g r ee$ InDegree та $O u t D e g r ee$ OutDegree. Черга $q$ використовується в алгоритмі Кана. У $p r o b [v]$ prob[v] обчислюємо ймовірність потрапляння у вершину $v$ .

vector<vector<int>> g;
vector<int> InDegree, OutDegree;
deque<int> q;
vector<double> prob;

Зчитаємо кількість островів $n$ , кількість мостів $m$ та індекс стартового острова $r$ . Ініціалізуємо список суміжності та масиви степенів.

scanf("%d %d %d", &n, &m, &r);
g.assign(n + 1, vector<int>());
InDegree.assign(n + 1, 0);
OutDegree.assign(n + 1, 0);

Зчитаємо мости та побудуємо граф. Для кожного ребра $a \to b$ a \to b збільшимо вихідний степінь вершини $a$ та вхідний степінь вершини $b$ .

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  OutDegree[a]++;
  InDegree[b]++;
}

C++

Додамо до черги всі вершини з нульовим вхідним степенем — топологічне сортування починається саме з них.

for (i = 1; i < InDegree.size(); i++)
  if (InDegree[i] == 0) q.push_back(i);

Ймовірність перебування у стартовій вершині $r$ дорівнює $1$ . Для всіх інших вершин початкова ймовірність дорівнює $0$ : функція $r es i z e$ заповнює масив $p r o b$ нулями.

prob.resize(n + 1);
prob[r] = 1;

Запустимо алгоритм Кана. Вершини вилучаються з черги у топологічному порядку.

while (!q.empty())
{

Вилучимо вершину $v$ з черги. На цей момент усі її попередники вже оброблені, тож значення $p r o b [v]$ prob[v] остаточне. Переберемо ребра $(v, t o)$ (v, to). З вершини $v$ виходить $O u t D e g r ee [v]$ OutDegree[v] ребер, і кожне з них обирається з однаковою ймовірністю. Тому ми переходимо по ребру $v \to t o$ v \to to з ймовірністю $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v]. Додамо це значення до $p r o b [t o]$ prob[to].

  v = q.front(); q.pop_front();
  for (int to : g[v])
  {
    prob[to] += prob[v] / OutDegree[v];

Видалимо ребро $(v, t o)$ (v, to) з графа — зменшимо вхідний степінь вершини $t o$ .

    InDegree[to]--;

Якщо вхідний степінь вершини $t o$ стає нульовим, усі її попередники оброблені, і значення $p r o b [t o]$ prob[to] остаточне. Додамо $t o$ до черги.

    if (InDegree[to] == 0) q.push_back(to);
  }
}

Знайдемо максимальну ймовірність $m x$ серед тупикових вершин — островів $i$ без вихідних мостів ( $O u t D e g r ee [i] = 0$ OutDegree[i] = 0).

mx = 0;
for (i = 1; i <= n; i++)
  if (OutDegree[i] == 0 && prob[i] > mx) mx = max(mx, prob[i]);

Виведемо, у порядку зростання, індекси всіх тупикових вершин, ймовірність яких відрізняється від $m x$ не більше ніж на $E P S$ . Таких вершин може бути декілька.

for (i = 1; i <= n; i++)
  if (OutDegree[i] == 0 && fabs(prob[i] - mx) <= EPS)
    printf("%d ", i);