Atcoder Educational DP Contest G - Longest Path

View as PDF
Submit solution
Points: 0.03 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout
Suggester:
takerevenge
Problem source:
Atcoder Educational DP Contest
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho đồ thị có hướng ~G~ có ~N~ đỉnh và ~M~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~N~, và cạnh có hướng thứ ~i~ ~(1 \leq i \leq M)~ đi từ đỉnh ~x_i~ tới đỉnh ~y_i~.

Đảm bảo rằng đồ thị ~G~ không có chu trình.

Tìm độ dài đường đi có hướng dài nhất trong đồ thị ~G~, quy ước rằng: độ dài của một đường đi có hướng là số cạnh nằm trên đường đi đó.

Input

  • Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~, lần lượt là số đỉnh và số cạnh của đồ thị đã cho. ~(2 \leq N \leq 10^5 , 1 \leq M \leq 10^5 ) ~

  • Dòng thứ ~i~ trong số ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i~ và ~y_i~, biểu diễn cho cạnh thứ ~i~ của đồ thị.

Đảm bảo rằng tất cả các cạnh ~(x_i, y_i)~ bất kì đều phân biệt và đồ thị ~G~ không có chu trình.

Outout

In ra độ dài của đường đi có hướng dài nhất trong đồ thị ~G~.

Sample 1

Input
4 5
1 2
1 3
3 2
2 4
3 4
Output
3
Giải thích

Đường màu đỏ trong hình dưới đây là đường đi dài nhất:

Sample 2

Input
6 3
2 3
4 5
5 6
Output
2
Giải thích

Đường màu đỏ trong hình dưới đây là đường đi dài nhất:

Sample 3

Input
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
Output
3
Giải thích

Đường màu đỏ trong hình dưới đây là đường đi dài nhất:

Comments

Please read the guidelines before commenting.


  • 0
    ITK14_GiaBao  commented on Feb. 6, 2026, 11:52 a.m.

    dp tren cay a:)?


  • 0
    dailamsiu  commented on Dec. 17, 2025, 3:04 a.m.

    siu


  • 0
    TealHa  commented on Dec. 2, 2025, 1:43 p.m.

    Bài này đệ quy có nhớ là xong nha

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> a[100005];
int dp[100005];
int dfs(int u) {
    if (dp[u] != -1) return dp[u];
    int maxa{};
    for (auto& v : a[u]) maxa = max(maxa, dfs(v) + 1);
    return dp[u] = maxa;
}
int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        a[u].push_back(v);
    }
    memset(dp, -1, sizeof dp);
    int ans{};
    for (int i = 1; i <= n; i++) ans = max(ans, dfs(i));
    cout << ans;
}

  • 0
    vominhmanh10  commented on Nov. 4, 2025, 11:38 a.m.

    à sắp topo để biết duyệt dp cái nào trước

    import sys

sys.setrecursionlimit(10**7)
data = sys.stdin.read().split()

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)
    topo.append(u)

n, m = map(int, data[0:2])
adj = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = map(int, data[2 + 2 * i:4 + 2 * i])
    adj[u].append(v)
topo = []
visited = [False] * (n + 1)
for u in range(1, n + 1):
    if not visited[u]:
        dfs(u)
topo.reverse()
dp = [0] * (n + 1)
for i in range(n):
    u = topo[i]
    for v in adj[u]:
        dp[v] = max(dp[v], dp[u] + 1)
print(max(dp))

  • -4
    tandochuyentin2022  commented on April 12, 2024, 6:39 a.m.

    orz


  • -82
    Ducanh_ils  commented on Dec. 16, 2023, 2:56 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -53
      Ducanh_ils  commented on Jan. 3, 2024, 8:02 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -53
        Ducanh_ils  commented on Jan. 3, 2024, 8:02 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


  • -54
    Ducanh_ils  commented on Dec. 16, 2023, 2:56 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -7
      DucNguyenNoob  commented on Jan. 3, 2024, 8:24 a.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -37
      Ducanh_ils  commented on Jan. 3, 2024, 8:03 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -40
        Ducanh_ils  commented on Jan. 3, 2024, 8:03 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


    • -10
      nhatquang1310  commented on Jan. 1, 2024, 3:24 p.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -9
        avgnoob1  commented on Jan. 3, 2024, 9:07 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


      • -23
        Ducanh_ils  commented on Jan. 3, 2024, 8:05 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


    • -37
      HoaBanMaTuy  commented on Dec. 16, 2023, 3:03 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.