Solutions of Longest path - MarisaOJ: Marisa Online Judge

Solutions of Longest path

Select solution language

Write solution here.


ducyn    Created at    1 likes

**1. Mô hình bài toán** * Cho đồ thị có hướng với `n` đỉnh và `m` cạnh. * Ta cần tìm **độ dài lớn nhất của đường đi** (tính theo số đỉnh) trong đồ thị này. Ví dụ: Nếu đường đi dài nhất là `1 → 3 → 5 → 7` thì độ dài sẽ là `4`. --- **2. Ý tưởng** Bài toán **đường đi dài nhất trong DAG** có thể giải bằng **Topological Sort + Quy hoạch động**: 1. **Bậc vào (`in[]`)**: Lưu số cạnh đi vào mỗi đỉnh. 2. **Độ dài đường đi (`d[]`)**: * `d[i]` là độ dài lớn nhất của đường đi kết thúc tại đỉnh `i`. * Ban đầu mọi `d[i] = 1` vì đường đi ngắn nhất chỉ chứa chính nó. 3. **Thuật toán**: * Bắt đầu từ tất cả đỉnh có bậc vào bằng 0 (không phụ thuộc ai). * Dùng hàng đợi (BFS topo): * Lấy đỉnh `u` ra khỏi hàng đợi. * Với mỗi cạnh `u → v`: * Giảm bậc vào `in[v]`. * Cập nhật `d[v] = max(d[v], d[u] + 1)`. * Nếu `in[v] == 0` thì cho vào hàng đợi. 4. **Kết quả**: Độ dài lớn nhất là `max(d[1..n])`. --- **3. Độ phức tạp** * **Thời gian**: $O(n + m)$ * **Bộ nhớ**: $O(n + m)$ --- Code tham khảo: ```cpp #include <bits/stdc++.h> #define ll long long #define name "TASK" using namespace std; const int MAXN=1e5; int n, m, in[MAXN], d[MAXN]; vector<int> adj[MAXN]; void inp(){ cin>>n>>m; for(int i=0;i<m;i++){ int x, y; cin>>x>>y; adj[x].push_back(y); in[y]++; } for(int i=0;i<MAXN;i++) d[i]=1; } void topo(){ queue<int> q; for(int i=1;i<=n;i++){ if(in[i] == 0) q.push(i); } while(!q.empty()){ int u=q.front(); q.pop(); for(int v:adj[u]){ in[v]--; d[v]=d[u]+1; if(in[v]==0) q.push(v); } } cout<<*max_element(d, d+n); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen(name ".INP", "r")) { freopen(name ".INP", "r", stdin); freopen(name ".OUT", "w", stdout); } inp(); topo(); return 0; } ```