Довгий шлях#11452

Довгий шлях (Розбір)

Знайдемо топологічне сортування графа. Позначимо через $d p [u]$ максимальну кількість міст, яке можна відвідати по шляху, починаючи з вершини $u$ .

Розглянемо вершини в порядку топологічного сортування. Нехай $u$ — поточна вершина. Позначимо через $v_{1}, v_{2}, ..., v_{k}$ v_1, v_2, ..., v_k вершини, до яких ведуть ребра з $u$ . Тоді оновимо значення:

d p [u] = ma x (d p [v_{i}] + 1), 1 \leq i \leq k

dp[u] = max(dp[v_i] + 1), 1 \le i \le k

Спочатку встановимо $d p [u] = 0 (1 \leq u \leq n)$ dp[u] = 0~(1 \le u \le n).

Після обробки всіх вершин знаходимо найбільше значення в масиві $d p$ . Воно дорівнює довжині максимального шляху в графі.

Приклад

Ліворуч наведено граф із першого прикладу. Праворуч — із другого. Найдовші шляхи виділені.

У першому прикладі найдовший шлях дорівнює $d p_{1} = 3$ dp_1 = 3.

У другому прикладі найдовший шлях дорівнює $d p_{4} = 2$ dp_4 = 2.

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

Оголосимо список суміжності графа $g$ .

vector<vector<int> > g;

Функція dfs виконує пошук у глибину, починаючи з вершини $v$ . Сортуємо вершини графа топологічно і записуємо їх в масив $t o p$ .

void dfs(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (used[to] == 0) dfs(to);
  top.push_back(v);
}

C++

Основна частина програми. Читаємо вхідні дані. Будуємо список суміжності орієнтованого графа.

scanf("%d %d", &n, &m);
g.resize(n + 1);
while (m--)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
}

C++

Запускаємо пошук у глибину на несв'язаному графі.

used.resize(n + 1);
for (i = 1; i <= n; i++)
  if (used[i] == 0) dfs(i);

Перебираємо вершини графа в порядку, зворотному до їх топологічного сортування, тобто перебираємо вершини масиву $t o p$ зліва направо.

dp.resize(n + 1);
for (int u : top)
{

Шлях з вершини $u$ в саму себе має довжину $0$ (ініціалізація).

  dp[u] = 0;

Перебираємо вершини $v$ , суміжні з $u$ . Розглядаємо ребро $(u, v)$ .

  for (int v : g[u])

Для всіх таких вершин $v$ шукаємо максимум серед значень $d p [v] + 1$ dp[v] + 1.

    dp[u] = max(dp[u], dp[v] + 1);
}

Знаходимо і виводимо найбільший елемент у масиві $d p$ . Він відповідає довжині найдовшого шляху в графі.

res = *max_element(dp.begin(), dp.end());
printf("%d\n", res);