Бакинське метро#11865

Бакинське метро (Розбір)

Схема метро являє собою зв'язний неорієнтований граф з $n$ вершин та $n$ рёбер. Зв'язний граф на $n$ вершинах, що містить рівно $n - 1$ n - 1 ребро, є деревом. Додавання ще одного ребра до дерева створює рівно один цикл. Тому граф з умови складається з єдиного циклу (кільцевої лінії), до вершин якого підвішені дерева (можливо, порожні).

Для кожної вершини потрібно знайти довжину найкоротшого шляху до найближчої вершини циклу. Для вершин циклу відповідь дорівнює $0$ . Задача розв'язується у два етапи.

Етап 1. Виділення циклу: послідовне видалення листків

Обчислимо ступені всіх вершин. Помістимо в чергу всі вершини ступеня $1$ , тобто листки. Поки черга не порожня, видобуваємо з неї вершину $v$ і позначаємо її як видалену. Потім зменшуємо на $1$ ступінь кожного її сусіда, який ще не видалений. Якщо ступінь сусіда став рівним $1$ , то він сам перетворився на листок, і ми додаємо його в чергу.

Після завершення процесу невидаленими залишаться тільки вершини циклу. Це випливає з двох спостережень:

Вершина циклу ніколи не стане листком. У неї завжди є два сусіди по циклу, а вони теж не видаляються. Строго це доводиться індукцією за кроками процесу.
Кожна вершина висячого дерева буде видалена. Видалення листків "обгризає" дерево знизу вгору, від листків до точки прикріплення до циклу. Ця процедура аналогічна топологічному сортуванню за алгоритмом Кана, лише застосованому до неорієнтованого графа.

Етап 2. Багатоджерельний пошук у ширину

Покладемо $d [v] = 0$ d[v] = 0 для всіх вершин циклу та $d [v] = -1$ d[v] = –1 (не відвідана) для решти. Помістимо всі вершини циклу в чергу одночасно та запустимо з них пошук у ширину. Коли вершина $u$ видобувається з черги, кожен її невідвіданий сусід $w$ отримує значення $d [w] = d [u] + 1$ d[w] = d[u] + 1 і додається в чергу.

Пошук у ширину з множини джерел обробляє вершини у порядку незменшення відстані до цієї множини. Тому $d [v]$ дорівнює мінімальній кількості переходів від $v$ до кільцевої лінії. Оскільки все, що лежить поза циклом, є деревом, шлях від кожної станції до кільця насправді єдиний.

Поки в графі є вершини ступеня $1$ , видаляємо їх.
Коли таких вершин більше не залишиться, у графі залишаться тільки вершини, що утворюють цикл.

Цей процес нагадує зворотне топологічне сортування: ми послідовно видаляємо листки, поки не залишаться тільки "внутрішні" вершини — саме вони і становлять цикл.

Далі запускаємо пошук у ширину одночасно з усіх вершин, що входять до циклу. Таким чином для кожної вершини, що залишилася, визначаємо мінімальну кількість кроків (переходів) до найближчої вершини кільця.

Приклад

У першому прикладі всі вершини входять до одного циклу, тому відстань для кожної з них дорівнює $0$ .

У другому прикладі цикл утворюють вершини $2, 3$ та $5$ , а решта вершин знаходяться на деякій відстані від нього.

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

Оголосимо список суміжності графа $g$ , а також допоміжні масиви:

$u se d$ — ознака видалення вершини: $u se d [v] = 1$ used[v] = 1, якщо вершина $v$ вже видалена як листок, і $u se d [v] = 0$ used[v] = 0, якщо вона ще залишається у графі. Після завершення першого етапу нульові значення збережуться тільки у вершин циклу;
$d i s t$ — масив відстаней: $d i s t [v]$ dist[v] дорівнює числу переходів від вершини $v$ до найближчої вершини циклу (значення $-1$ означає, що вершина ще не відвідана);
$d e g$ — поточні ступені вершин: $d e g [v]$ deg[v] дорівнює кількості сусідів вершини $v$ , які ще не видалені.

Черга $q$ використовується на обох етапах алгоритму: спочатку для послідовного видалення листків, потім для багатоджерельного пошуку в ширину.

vector\u003cvector\u003cint\u003e \u003e g;
vector\u003cint\u003e used, dist, deg;
queue\u003cint\u003e q;

Читаємо вхідні дані. Будуємо граф.

scanf("%d", \u0026n);
g.resize(n + 1);
for (i = 0; i \u003c n; i++)
{
  scanf("%d %d", \u0026a, \u0026b);
  g[a].push_back(b);
  g[b].push_back(a);
}

C++

Обчислюємо початкові ступені вершин: ступінь вершини $i$ дорівнює розміру її списку суміжності $g [i]$ . Усі листки, тобто вершини ступеня $1$ , заносимо в чергу $q$ і одразу позначаємо як видалені $(u se d [i] = 1)$ (used[i] = 1).

used.resize(n + 1, 0);
deg.resize(n + 1, 0);
for (i = 1; i \u003c= n; i++)
{
  deg[i] = g[i].size();
  if (deg[i] == 1)
  {
    q.push(i);
    used[i] = 1;
  }
}

C++

Послідовно видаляємо листки. Зовні цей цикл схожий на пошук у ширину, однак вершина потрапляє в чергу не при першому виявленні, а тільки тоді, коли сама стає листком. Видобуваємо з черги вершину $v$ і перебираємо її сусідів $t o$ . Сусідів, уже позначених як видалені, пропускаємо. Для кожного невидаленого сусіда зменшуємо ступінь на $1$ , оскільки ребро $(v, t o)$ (v, to) зникає з графа разом з вершиною $v$ .

while (!q.empty())
{
  int v = q.front(); q.pop();
  for (int to : g[v])
    if (used[to] == 0)
    {
      deg[to]--;

C++

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

      if (deg[to] == 1)
      {
        q.push(to);
        used[to] = 1;
      }
    }
}

C++

На даний момент рівність $u se d [i] = 0$ used[i] = 0 виконується тоді і тільки тоді, коли вершина $i$ належить циклу.

Ініціалізуємо масив $d i s t$ значенням $-1$ (усі вершини не відвідані). Черга на цей момент уже порожня, але присвоєння порожньої черги явно скидає її перед другим обходом. Потім кожну вершину циклу заносимо в чергу і покладаємо для неї $d i s t [i] = 0$ dist[i] = 0 — усі вершини кільцевої лінії одночасно стають джерелами пошуку в ширину.

dist = vector\u003cint\u003e(n + 1, -1);
q = queue\u003cint\u003e();
for (i = 1; i \u003c= n; i++)

  if (used[i] == 0)
  {
    q.push(i);
    dist[i] = 0;
  }

C++

Запускаємо багатоджерельний пошук у ширину. Видобуваємо з черги вершину $v$ . Кожен її невідвіданий сусід $t o (d i s t [t o] = -1)$ to~(dist[to] = –1) отримує відстань $d i s t [v] + 1$ dist[v] + 1 і заноситься в чергу. Вершини циклу позначені відстанню $0$ з самого початку, тому обхід не повертається на кільце і поширюється тільки вглиб висячих дерев. Оскільки вершини видобуваються з черги у порядку незменшення відстані, кожне значення $d i s t [t o]$ dist[to] є найкоротшим.

while (!q.empty())
{
  int v = q.front(); q.pop();
  for (int to : g[v])
    if (dist[to] == -1)
    {
      q.push(to);
      dist[to] = dist[v] + 1;
    }
  }

C++

Виводимо відстані від станцій до кільцевої лінії у порядку їхніх номерів.

for (i = 1; i \u003c= n; i++)
   printf("%d ", dist[i]);
printf("\n");