Почему этот алгоритм не находит самый длинный путь в ориентированном графике ацикли c?

Question

Я пытался использовать динамическое c программирование для решения этого вопроса. dp [i] хранит самый длинный путь, заканчивающийся на i. Для каждого ребра от x до y я обновляю dp [y] до максимума между dp [y] и dp [x + 1].

Он работает на примерах ввода-вывода, но не работает в некоторых тестовых случаях, пока быть судимым. Не смог придумать ни одного тестового случая, в котором он бы провалился. Буду признателен за любую помощь.

N - количество вершин
M - количество ребер
xy обозначает ребро из от x до y
Выходные данные должны быть длиной самого длинного пути на графике.

• Пример ввода
  NM
  x1 y1
  x2 y2
  x3 y3
  .
  .
  .
  Вход 1
  4 5
  1 2
  1 3
  3 2
  2 4
  3 4
  Выход 1
  3
  Вход 2
  5 8
  5 3
  2 3
  2 4
  5 2
  5 1
  1 4
  4 3
  1 3
  Выход 2
  3

#include <bits/stdc++.h>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m;
    cin>>n>>m;

    vector<int> dp(n+1,0);
    //dp[i] denotes max length of path ending at node i
    int x,y;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        dp[y]=max(dp[x]+1,dp[y]);
    }
    int ans=0;
    // for(int i=0;i<n+1;i++)
    //  cout<<i<< " : "<<dp[i]<<endl;
    for(int i=0;i<n+1;i++)
        ans=max(ans,dp[i]);
    cout<<ans<<endl;
}

Answer 1

Проблема здесь в том, что, хотя вы действительно обрабатываете каждое ребро, вы обрабатываете их в порядке, который не гарантирует, что вы действительно обнаружите нужные пути. Например, рассмотрим этот DAG:

1 -> 2 -> 3

Представьте, что входной файл имеет ребра в следующем порядке:

2 3
1 2

Первоначально dp [1], dp [2] и dp [3] все ноль. После просмотра первой строки dp [2] устанавливается на 1, а после второй dp [1] также устанавливается на 1. Однако эти окончательные значения неверны, потому что dp [2] должно быть 2.

Причина, по которой это не удается, заключается в том, что рассматриваемое вами решение DP работает, только если вы посещаете ребра в топологическом порядке, в котором каждый раз, когда вы видите ребро от x до y, вы знаете, что уже вычислили длину самого длинного пути до x, прежде чем подумать об обновлении y.

Чтобы это исправить, сохраните ребра, которые вы прочитали, и посетите ребра в топологическом порядке узлов. Вы можете найти топологические заказы разными способами, и я оставлю вам детали. : -)

Надеюсь, это поможет!