# **Topological sort**
- Một đồ thị tồn tại thứ tự Tô-pô khi và chỉ khi đồ thị đó là DAG. Đồng nghĩa, mọi DAG luôn tồn tại ít nhất một thứ tự Tô-pô, và có thuật toán để tìm thứ tự Tô-pô trong thời gian tuyến tính.
- Tính chất
- Thứ tự Tô-pô không nhất thiết phải duy nhất. Có thể có một số thứ tự Tô-pô khác nhau trong một đồ thị.
- Tuy nhiên , thứ tự Tô-pô sẽ là duy nhất khi DAG có đường đi Hamilton.
> Thuật toán 1
1. - Bắt đầu với một danh sách Tô-pô trống.
2. - Tìm đỉnh nguồn của DAG. Thêm đỉnh này vào cuối danh sách Tô-pô.
3. - Loại bỏ đỉnh này và tất cả các cạnh kề với nó ra khỏi DAG.
4. - Nếu số đỉnh của DAG lớn hơn 0, hãy quay lại bước 2.
- Nhận xét:
- Một đỉnh là nguồn khi và chỉ khi số lượng cung vào của nó bằng 0.
- Nếu một đỉnh không phải là đỉnh nguồn, nó sẽ trở thành đỉnh nguồn sau khi tất cả các cung vào của nó đã bị xóa. Một cung vào của nó chỉ bị xóa khi đỉnh còn lại của cung đó bị xóa.
- Giả sử ta biết vị trí của tất cả đỉnh nguồn trong DAG và ta thực hiện các bước 2 và 3 một lần. Sau đó, những đỉnh duy nhất có thể trở thành đỉnh nguồn là những đỉnh có cung vào nối với đỉnh vừa bị xóa.

#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;

int n, m;
int indegree[maxn], ans[maxn];
vector<int> g[maxn], topo;
queue<int> listSource;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
	
	cin >> n >> m;
	while (m--) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		indegree[v]++;
	}	
	for (int u = 1; u <= n; u++) {
		if (!indegree[u]) listSource.push(u);
	}
	while (!listSource.empty()) {
		int u = listSource.front();
		listSource.pop();
		topo.push_back(u);
		for (auto v: g[u]) {
			indegree[v]--;
			if (!indegree[v]) listSource.push(v);
		}
	}
	if (topo.size() < n) {
		cout << "Error: graph contains a cycle";
		return 0;
	}
	int cnt = 0;
	for (auto x: topo) ans[x] = ++cnt;
	for (int i = 1; i <= n; i++) cout << ans[i] << " ";
	return 0;
}
DPT: O(n + m)

> Thuật toán 2
1. - Xuất phát từ một điểm chưa được duyệt, ta bắt đầu duyệt DFS trên đồ thị xuất phát từ điểm đó.
2. - Dùng một mảng để lưu trạng thái của mỗi đỉnh. Có 3 trạng thái:
- **Trạng thái 0**: Đỉnh chưa được duyệt (chưa từng được gọi hàm DFS).
- **Trạng thái 1**: Đỉnh vẫn đang duyệt (hàm DFS với đỉnh này chưa kết thúc).
- **Trạng thái 2**: Đỉnh đã duyệt xong (hàm DFS với đỉnh này đã kết thúc).
3. - Hiển nhiên, khi đang duyệt mà ta gặp phải một đỉnh ở trạng thái 1 thì điều đó chứng tỏ đồ thị đang xét có chứa chu trình, và không thể sắp xếp Tô-pô được.
4. - Sau khi kết thúc duyệt DFS trên đồ thị, thứ tự hoàn tất duyệt của mỗi đỉnh chính là danh sách nghịch đảo của thứ tự Tô-pô.

#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;

int n, m;
int visit[maxn], ans[maxn];
vector<int> g[maxn];
stack<int> topo;

void dfs(int u) {
	
	visit[u] = 1;
	for (auto v: g[u]) {
		if (visit[v] == 1) {
			cout << "Error: graph contains a cycle";
			exit(0);
		}
		if (!visit[v]) dfs(v);
	}	
	topo.push(u);
	visit[u] = 2;
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
	
	cin >> n >> m;
	while (m--) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
	}	
	for (int i = 1; i <= n; i++) {
		if (!visit[i]) dfs(i);
	}
	int cnt = 0;
	while (!topo.empty()) {
		ans[topo.top()] = ++cnt;
		topo.pop();
	}
	for (int i = 1; i <= n; i++) cout << ans[i] << " ";
	return 0;
}
DPT: O(n + m)

> **LIST BÀI TẬP**
- [x] [Đường đi dài nhất](https://lqdoj.edu.vn/problem/longestpath)
- [x] [Fox And Names](https://codeforces.com/problemset/problem/510/C)
- [ ] [Giải bóng đá](https://oj.vnoi.info/problem/nkleague)
- [ ] [Thu hoạch](https://oj.vnoi.info/problem/kcollect)
- [ ] [Lò cò](https://oj.vnoi.info/problem/nkjump)
- [ ] [Vòng đua xe đạp](https://oj.vnoi.info/problem/bic)
- [ ] [TOPOSORT - Topological Sorting](https://www.spoj.com/problems/TOPOSORT/)
- [ ] [RPLA - Answer the boss!](https://www.spoj.com/problems/RPLA/)
- [ ] [Substring](https://codeforces.com/contest/919/problem/D)
- [ ] [Course Schedule](https://cses.fi/problemset/task/1679)
- [ ] [Longest Flight Route](https://cses.fi/problemset/task/1680)
- [ ] [Game Routes](https://cses.fi/problemset/task/1681)
- [ ] [List VNOI](https://vnoi.info/problems/list/?tag=117&page=1)

Thông tin về cách chứng minh chi tiết: [VNOI Wiki](https://vnoi.info/wiki/algo/graph-theory/topological-sort.md)