一、强联通分量
- 点互相可达的子图
二、Tarjan算法
- dfn[x]:时间戳，代表x是第几个被访问的点
- low[x]:代表x最多只经过一条非树边，能到达的点中，dfn的最小值（能到达的最浅点）
（此处应有图例）- 用途：缩点（缩点后为DAG）
三、双联通分量
- vDCC：点双联通分量
- eDCC：边双联通分量
四、二分图匹配：
- 性质：
- 二分图最小点覆盖 == 二分图最大匹配
- 二分图最大点独立集 = 总点数 - 二分图最大匹配
五、2-SAT
六、网络流
- Dinic、ISAP算法等
七、最小割
- 定义：图中所有割中，边权值和最小的割（经典模型：二分图最小点权覆盖）
- 对于任意最大流，其值等于最小割.
- 例题：Dining 吃饭 [Usaco 2007 Open]
八、最大点权独立集（基于二分图）
- 思路：先加权，后减去最大流.
九、费用流
- 常用方法：拆点
十、非负最大流