拓扑排序

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 874 字

删入度为 0 的点，无法排完说明有环

图论
拓扑排序

前置内容

正文

// 拓扑排序：有向无环图
// 每次删入度为 0 的点
// 队列维护候选，BFS 思想
// 无法排完说明有环
#include <cstdio>
int h[10005], nxt[200005], to[200005];
int cnt = 0, n, m, deg[10005], q[10005];
int hh = 0, tt = -1, tot = 0;
// 加边并增加终点入度
void add(int u, int v) {
    nxt[++cnt] = h[u];
    h[u] = cnt;
    to[cnt] = v;
    // v 的入度 +1
    deg[v]++;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
    }
    // 入度为 0 的点先入队
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0) q[++tt] = i;
    while (hh <= tt) {
        int u = q[hh++];
        // 每弹出一个算一个
        tot++;
        // 删边后 successor 入度 -1
        for (int e = h[u]; e; e = nxt[e]) {
            int v = to[e];
            if (--deg[v] == 0) q[++tt] = v;
        }
    }
    // tot<n 说明存在环
    printf("%s", tot == n ? "YES" : "NO");
    return 0;
}

拓扑排序

前置内容

正文

CSP-J · 编程模板的其它内容