**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;
}
```