模板及讲解

用queue来存入度为0的点，然后BFS即可

常见题型

1、图中DP
Q: 给你一张图，你要在上面DP
解: 拓扑序保证无后效性，用拓扑序来DP转移
例题: Codeforces 919D
2、图中判环/无环
Q: 给你一张图，判图中有环/无环
解: 拓扑排序必须无环，如果没有拓扑某些点则有环
例题: Codeforces 915D

相关代码

hdu1285

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
vector<int> G[505];
int n, m, ino[505], ino2[505], tot;
bool topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) if (ino2[i] == 0) tot++, q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i];
            ino2[v]--;
            if (ino2[v] == 0) tot++, q.push(v);
            if (ino2[v] < 0) ino2[v] = 0;
        }
    }
    if (tot == n) return 1; else return 0;
}
void clean() {
    tot = 0, ms(ino, 0);
}
int solve() {
    clean();
    for (int u, v, i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v), ino[v]++;
    }
    for (int i = 1; i <= n; i++) {
        memcpy(ino2, ino, sizeof ino);
        if (!ino2[i]) continue;
        ino2[i]--, tot = 0;
        if (topsort()) return printf("YES\n"), 0;
    }
    printf("NO\n");
    return 0;
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}