图论---拓扑排序

概念

        一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。一直进行上面的处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。拓扑排序是对DAG（有向无环图）上的节点进行排序，使得对于每一条有向边u->v，u 都在v之前出现。简单地说，是在不破坏节点先后顺序的前提下，把DAG拉成一条链。

算法过程

        构造拓扑序列步骤

1. 从图中选择一个入度为零的点。

2. 输出该顶点，从图中删除此顶点及其所有的出边。

重复上面两步，直到所有顶点都输出，拓扑排序完成，或者图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成，陷入死锁。

代码框架

int n;
vector<int> g[MAXN]; // 储存节点出边
int in[MAXN];  // 存储每个结点的入度
bool toposort() {vector<int> l; // 排序结果queue<int> q;for (int i = 0; i < n; i++){ // 入度为0的节点入队if (in[i] == 0) {q.push(i);}}while (!q.empty()) {int u = q.front();q.pop();l.push_back(u);for (auto v : G[u]) { // 删除与节点u直接相连的边if (--in[v] == 0) { // 出现新入度为零的节点入队q.push(v);}}}return l.size() == n;
}

题单

207. 课程表 - 力扣（LeetCode）

210. 课程表 II - 力扣（LeetCode）