Месники (Розбір)

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

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

Якщо $n\text{<}3$, неможливо вибрати три різні міста, і відповідь $-1$. Надалі вважаємо, що n \ge 3.

Будь-який шлях в ациклічному графі відвідує вершини в порядку їх топологічного сортування. Отже, якщо шлях містить вершини $x$ та $y$, то одна з них досяжна з іншої. Звідси випливає ключове спостереження: якщо існують дві вершини $x$ та $y$, такі що жодна з них не досяжна з іншої, то жоден шлях не проходить через обидві з них. Відповідно, не існує шляху і через трійку x, y, z, де $z$ — довільна третя вершина.

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

Твердження 1. Якщо в деякий момент черга одночасно містить дві вершини $x$ та $y$, то шляху між ними не існує.

Твердження 2. Якщо на кожному кроці алгоритму черга містить рівно одну вершину, то всі вершини графа лежать на одному шляху.

Таким чином, алгоритм наступний: виконуємо алгоритм Кана і перевіряємо розмір черги перед кожним вилученням. Як тільки він містить більше однієї вершини, беремо будь-які дві з них як $x$ та $y$, і будь-яку іншу вершину графа як $z$. Якщо такий момент так і не настане, виводимо $-1$.

Кожна вершина та кожне ребро обробляються не більше одного разу, тому часова складність алгоритму становить O(n + m), а використання пам'яті — O(n + m).

Приклад

Графи з тестових прикладів мають таку структуру:

• У першому прикладі черга містить одну вершину на кожному кроці: \{1\}, \{2\}, \{3\}. Граф містить шлях 1 \to 2 \to 3, що проходить через усі вершини, тому відповідь $-1$.

• У другому прикладі черга спочатку містить вершину $1$. Після її видалення вхідні степені вершин $2$ та $3$ стають нульовими, і обидві вони одночасно з'являються в черзі. Шляху між вершинами $2$ та $3$ не існує, тому можемо взяти x = 2, y = 3 та z = 1 як відповідь.

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

Оголосимо структури даних. Вхідний граф представлений списком суміжності $g$, а вхідні степені вершин зберігаються в масиві InDegree.

vector<vector<int> > g;
vector<int> InDegree;
deque<int> q;

Зчитаємо вхідні дані.

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

Для кожного ребра $(a,b)$ збільшуємо InDegree[b] на $1$.

  InDegree[b]++;
}

Усі вершини з нульовою вхідною степенню додаються до черги $q$.

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

Три шукані вершини зберігаються у змінних $x,y$ та $z$.

x = y = -1;

Продовжуємо виконувати алгоритм, доки черга $q$ не порожня.

while (!q.empty())
{

Якщо черга одночасно містить більше однієї вершини, це означає, що розв'язок знайдено.

  if (q.size() > 1)
  {
    x = q[0];
    y = q[1];
    break;
  }

Виймаємо вершину $v$ з черги — вона стане поточною вершиною в топологічному порядку.

  v = q.front(); q.pop_front();

Видаляємо з графа всі ребра вигляду (v, to). Для кожного такого ребра зменшуємо вхідну степінь вершини $to$. Якщо вхідна степінь $to$ стає нульовою, додаємо її до черги.

  for (int to : g[v])
  {
    InDegree[to]--;
    if (InDegree[to] == 0) q.push_back(to);
  }
}

Алгоритм Кана завершено. Якщо значення $x$ усе ще $-1$, це означає, що розв'язку не існує.

if (x == -1)
  printf("-1\n");
else
{

Якщо розв'язок існує, обираємо $z$ як найменшу вершину, відмінну від $x$ та $y$.

  z = 1;
  while (z == x || z == y) z++;
    printf("%d %d %d\n", x, y, z);
}