前置知识
强连通分量（SCC）
Tarjan算法
Gabow算法
定义
简单来理解，就算把强连通分量当成一个点，从而实现简化图的目的。
缩点后的图要保留所有不在分量里的边，而且缩点后的图是一个有向无环图(DAG)，也就是说可以进行拓扑排序。
应用
标准问法
给你一张有向图，每个点都有一个点权（不是边权了！！！），且每一个点都可以经过任意多次，但是点权只能加一次，求这张图的最大权值
问题解析
此处不能使用最短路进行修改求最长路（会进入死循环！！！）
正解：缩点得出DAG+动态规划求最大值
上一篇
Tarjan算法2022-06-28
下一篇
强连通分量（SCC）图论基础-强连通分量
2022-06-28