\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.6}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày trâu>}}\)

• \(\color{#903030}{\text{<Cày trâu>}}\) Với mỗi đỉnh \(u\). Duyệt xem độ dài xa nhất của nó trong các đỉnh con \(v\) là bao nhiêu

• \(\color{#903030}{\text{<Phân tích độ phức tạp>}}\) Mỗi đỉnh ta sẽ duyệt qua \(O(V)\) hậu duệ của nó.

Với ma trận : \(O(V^3)\) với \(V\) là số đỉnh. Vì để tìm các đỉnh con mất thêm \(O(V)\)

Với danh sách kề: \(O(V \times E^2) = O(V^3)\) và cải tiến bằng sắp xếp với chặt nhị phân \(O(V \times E \log E) = O(V^2 \log V)\) . Vì để tìm các đỉnh con mất thêm mất \(O(E)\) khi mảng chưa sort và mảng đã sort mất \(O(\log E)\)

Với danh sách liên kết: \(O(V^2)\) với \(V\) là số đỉnh. Vì các đỉnh tiếp theo sẽ được duyệt lần lượt trong tập các đỉnh con của đỉnh đang xét nên chỉ mất \(O(1)\) việc tìm kiếm

\(\color{#300000}{\text{Hint 2 <Quy hoạch động>}}\)

• \(\color{#903030}{\text{<Cày trâu>}}\) Với mỗi đỉnh \(u\). Duyệt xem độ dài xa nhất của nó trong các đỉnh con gốc \(v\) là bao nhiêu. Và lưu kết quả vào \(f[u]\)

• \(\color{#903030}{\text{<Phân tích độ phức tạp>}}\) Nếu ta duyệt đến đỉnh \(u\) thì \(f[u]\) tất cả con, cháu, chắt, chít, ... \(v\) của \(u\) là \(f[v]\) cũng đã đều được tính một và chỉ một lần. Lần sau khi bị gọi lại nó sẽ trả về kết quả \(f[u]\) thay vì tính lại từ đầu. Nên sẽ giảm được \(O(V)\) so với việc cày trâu như trên

Với ma trận : \(O(V^2)\) với \(V\) là số đỉnh

Với danh sách kề: \(O(E^2) = O(V^2)\) và cải tiến bằng sắp xếp với chặt nhị phân \(O(E \log E) = O(V \log V)\)

Với danh sách liên kết: \(O(V)\) với \(V\) là số đỉnh

\(\color{#009933}{\text{Code tham khảo<Accepted> }}\): Approach

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(V)\ \color{#7f5f3f}{\text{time}}\ ||\ O(E)\ \color{#7f5f3f}{\text{memory}}}}\)

int n, m;
vector<vector<int> > G;
vector<int> f;
void maximize(int &res, int val) { if (res < val) res = val; }
int dfs(int u)
{
    if (f[u] != -1) return f[u];

    f[u] = 0;
    for (int v : G[u])
        maximize(f[u], dfs(v) + 1);

    return f[u];
}

int main()
{
    cin >> n >> m;
    G.resize(n + 1);
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    int res = 0;
    f.assign(n + 1, -1);
    for (int u = 1; u <= n; ++u)
        maximize(res, dfs(u));

    cout << res;
    return 0;
}