dfs:
无向图: 证明, 构造, 一条非树边对应一个环.
有向图: 只有前向边和树枝边从 dfn 小的点指向 dfn 大的点.
bfs:
无向图: 边只会在同层或相差不超过一层的点之间.
有向图: 满足 \(d(u)+w(u,v)~\ge~d(v)~~(w(u,v)\)是指 \(u\)到 \(v\)的路径 \()\).
SCC:
\(1.\)缩点成 DAG.
\(2.\)竞赛图 (任意两点都至少有单向边) 缩点后是一条链, 可以动态维护强连通性.
DCC:
\(1.\)把 \(E-DCC\)缩成树.
\(2.\)把点双建成圆方树(原图中任意两点的路径的并等价于圆方树上两点的路径).
\(3.\)动态维护双连通性.
最短路:
\(1.\)删点 / 边后维护最短路: 在最短路树上操作.
\(2.\)有零环时最短路图不一定是 DAG.
\(3.\)边权小时,\(dijkstra\)可以用桶代替堆(总共只 for 一遍).
\(4.\)差分约束系统:\(f(x)-f(y)\le w(x,y)\)能够转化成最短路, 差分或前缀和为变量.
欧拉回路:
\(1.\)有向 / 无向图上欧拉 (回) 路的求法.
- problems:
- USACO2018Dec Platinum C
- ASC 17C Forbidden Subwords
- SGU 307 Cipher
- codeforces 875F
- BZOJ3569 (杜教黑科技)
- HDU 6408 Card Game
- Codeforces 936E Iqea
- gym 100739H Molecules
来源: http://www.bubuko.com/infodetail-2996644.html