Atcoder Educational DP Contest G - Longest Path

Xem dạng PDF
Gửi bài giải
Điểm: 0,20 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Người đăng:
takerevenge
Nguồn bài:
Atcoder Educational DP Contest
Dạng bài
Ngôn ngữ cho phép
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:

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    dailamsiu  đã bình luận lúc 17, Tháng 12, 2025, 3:04

    siu


  • 0
    TealHa  đã bình luận lúc 2, Tháng 12, 2025, 13:43

    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  đã bình luận lúc 4, Tháng 11, 2025, 11:38

    à 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  đã bình luận lúc 12, Tháng 4, 2024, 6:39

    orz


  • -80
    Ducanh_ils  đã bình luận lúc 16, Tháng 12, 2023, 2:56

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -52
      Ducanh_ils  đã bình luận lúc 3, Tháng 1, 2024, 8:02

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -52
        Ducanh_ils  đã bình luận lúc 3, Tháng 1, 2024, 8:02

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -53
    Ducanh_ils  đã bình luận lúc 16, Tháng 12, 2023, 2:56

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -7
      DucNguyenNoob  đã bình luận lúc 3, Tháng 1, 2024, 8:24 ← chỉnh sửa

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -36
      Ducanh_ils  đã bình luận lúc 3, Tháng 1, 2024, 8:03

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -39
        Ducanh_ils  đã bình luận lúc 3, Tháng 1, 2024, 8:03

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -10
      nhatquang1310  đã bình luận lúc 1, Tháng 1, 2024, 15:24 ← chỉnh sửa

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -9
        avgnoob1  đã bình luận lúc 3, Tháng 1, 2024, 9:07

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -23
        Ducanh_ils  đã bình luận lúc 3, Tháng 1, 2024, 8:05

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -37
      HoaBanMaTuy  đã bình luận lúc 16, Tháng 12, 2023, 3:03

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.