Editorial for Atcoder Educational DP Contest G - Longest Path
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Độ phức tạp thời gian: ~O(N + M)~
Bài này đơn giản chỉ cần sử dụng thuật toán DFS trên đồ thị.
Định nghĩa ~dp[i]~ là độ dài đường đi có hướng dài nhất xuất phát từ ~i~. Chú ý cách tối ưu cấu trúc con: Độ dài đường đi có hướng dài nhất xuất phát từ ~i~ = độ dài đường đi dài nhất lớn nhất xuất phát từ một trong các con của ~i~ cộng thêm ~1~.
Hướng dẫn cài đặt:
#include <bits/stdc++.h> using namespace std; vector<int> dp(100001); vector<vector<int>> adj(100001); int dfs(int x) { if (dp[x]) return dp[x]; for (auto e : adj[x]){ dp[e] = dfs(e); dp[x] = max(dp[e] + 1, dp[x]); } return dp[x]; } int main(){ int n,m; cin >> n >> m; for(int i = 0; i < m; ++i) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); } for (int i = 0; i < n; ++i) { dfs(i); } int ans = 0; for (int i = 0;i < n; ++i) { ans = max(dp[i], ans); } cout << ans; }
Comments