图论基础概念
图 ( G ) 由点集 ( V ) 和边集 ( E ) 构成，记为 ( G=(V,E) )。无向图中边 ( e\in E ) 为无序对 ((u,v))，有向图中边为有序对 ( u\to v ) 或 ((u,v))。
- 简单图：不含重边和自环的图。
- 树：不含环的无向连通图，满足 ( n=m+1 )（n 为点数，m 为边数）。
- 有向无环图（DAG）：不含环的有向图。
拓扑排序
针对 DAG 的一种排序方式，要求对于图中任意边 ( u\to v )，u 在排序结果中位置始终在 v 之前。
实现思路：
- 维护入度为 0 的点的队列
- 每次取出一个入度为 0 的点加入结果序列
- 删去该点及其所有出边，更新相关点的入度
- 重复步骤 2-3 直至队列空
void Sort() {queue<int> q;for (int i = 1; i <= n; ++i) {if (inDegree[i] == 0) q.push(i);}while (!q.empty()) {int u = q.front();q.pop();res.push_back(u);for (int v : adj[u]) {if (--inDegree[v] == 0) q.push(v);}}
}