**Ý tưởng giải**
1. **Mô hình hóa đồ thị**
* Sử dụng danh sách kề `adj[u]` để lưu các đỉnh kề từ u.
* Mảng `in[v]` lưu **bậc vào** của mỗi đỉnh v (số cạnh đi vào v).
2. **Thuật toán Kahn (BFS cho Topo Sort)**
* Bước 1: Tìm tất cả các đỉnh có bậc vào bằng 0 (không phụ thuộc vào đỉnh nào khác) và đưa vào hàng đợi.
* Bước 2: Lấy từng đỉnh ra khỏi hàng đợi:
* Thêm đỉnh đó vào kết quả `res`.
* Giảm bậc vào của các đỉnh kề xuống 1.
* Nếu một đỉnh kề có bậc vào = 0 → đưa vào hàng đợi.
* Lặp lại đến khi hàng đợi rỗng.
3. **Kết quả**
* Mảng `res` chính là thứ tự topo hợp lệ.
* Nếu đồ thị là DAG (không có chu trình), sẽ in được hết n đỉnh.
---
**Độ phức tạp**
* **Thời gian**: $O(n + m)$ — duyệt qua mỗi đỉnh và mỗi cạnh đúng 1 lần.
* **Bộ nhớ**: $O(n + m)$ — lưu danh sách kề và bậc vào.
---
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];
vector<int> adj[MAXN], res;
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]++;
}
}
void topo(){
queue<int> q;
for(int i=1;i<=n;i++){
if(in[i] == 0){
q.push(i);
res.push_back(i);
}
}
while(!q.empty()){
int u=q.front(); q.pop();
for(int v:adj[u]){
in[v]--;
if(in[v]==0){
q.push(v);
res.push_back(v);
}
}
}
for(int x:res) cout<<x<<" ";
}
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;
}
```
ducyn
Created at
1 likes