图论

发表于2026-05-21|算法与竞赛

|浏览量:

这学期离散数学属实上的比线代舒爽太多因为很多知识点可以切实应用到代码实现，几乎是立即反馈。本篇可能比较杂乱，会慢慢整理，先挖好坑再说（）

文章作者: Bamboo_ming

文章链接: https://768910-bit.github.io/2026/05/21/%E5%9B%BE%E8%AE%BA/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源竹见！

相关推荐

最短路B3601 最短路问题（Bellman-Ford）B3601 [图论与代数结构 201] 最短路问题 - 洛谷这道题就是把每条边扫一遍。因为边的顺序不知道，所以需要跑 n-1 轮。每一轮把所有边都松一遍，同时用 flag 记录这一轮有没有发生更新——用来判定全局是否最优：如果一整轮扫下来没有任何更新，就说明已经改完了，可以提前退出。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<bits/stdc++.h>using namespace std;using ll=long long;#define endl '\n'struct Edge{ ll u,v,w;};const ll maxn=2e9;int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n&g...

拓扑排序拓扑序 = DAG 的线性化：把「u 在 v 前」的偏序展平成一条链。所以只有 DAG 才有拓扑序。队列弹出数 < n ⇒ 有环 —— 判环万能判据。 12345678// Kahn 模板骨架queue<int> q; for (i) if (!ind[i]) q.push(i);int cnt = 0;while (!q.empty()) { int u = q.front(); q.pop(); cnt++; for (v : e[u]) if (--ind[v] == 0) q.push(v);}// cnt < n , 有环 P1347 排序P1347 [ECNA 2001] 排序 - 洛谷这道题就是边排序边判断，其他都可以套模板。每读入一条关系就重跑一遍拓扑，返回三种状态： -1：弹出点数 cnt < n，说明有环，矛盾； 1：cnt == n 且队列任何时刻都只有一个元素（sure 没被置 false），说明拓扑序唯一，可以确定； 0：能排完但不唯一，信息不足，继续加关系。 1234567...

数据加载中