The longest Path#11452

The longest Path (Editoryal)

Let's find a topological sort of the graph. Denote by $d p [u]$ the maximum number of cities that can be visited along a path starting from vertex $u$ .

Consider the vertices in the order of the topological sort. Let $u$ be the current vertex. Let $v_{1}, v_{2}, ..., v_{k}$ v_1, v_2, ..., v_k be the vertices to which edges go from $u$ . Then update the value as follows:

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

Initially, set $d p [u] = 0 (1 \leq u \leq n)$ dp[u] = 0~(1 \le u \le n).

After processing all the vertices, find the greatest value in the $d p$ array. It equals the length of the longest path in the graph.

Example

On the left is the graph from the first example. On the right is the one from the second example. The longest paths are highlighted.

In the first example, the longest path equals $d p_{1} = 3$ dp_1 = 3.

In the second example, the longest path equals $d p_{4} = 2$ dp_4 = 2.

Algorithm implementation

Let's declare the adjacency list of the graph $g$ .

vector<vector<int> > g;

The function dfs performs a depth-first search starting from vertex $v$ . We topologically sort the vertices of the graph and store them in the array $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++

The main part of the program. Read the input data. Bild the adjacency list of the directed graph.

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

C++

Run a depth-first search on the disconnected graph.

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

Iterate over the vertices of the graph in the order opposite to their topological sort, that is, we iterate over the vertices in the $t o p$ array from left to right.

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

A path from vertex $u$ to itself has length $0$ (initialization).

  dp[u] = 0;

Iterate over the vertices $v$ adjacent to $u$ . Consider the edge $(u, v)$ .

  for (int v : g[u])

For all such vertices $v$ , find the maximum among the values $d p [v] + 1$ dp[v] + 1.

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

Find and print the largest element in the $d p$ array. It corresponds to the length of the longest path in the graph.

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