一般最短路 Floyd 传递闭包 可以使用 bitset 优化： 例题：洛谷 P4306[JSOI2010]连通数 题目大意： 给一个 $n$ 个点的有向图，其连通数指图中可达顶点对个的个数（包括自己和自己）。求图中的连通数 问题分析： 可以直接 Floyd 传递闭包搞。 如果上面做法被卡，可以先用 Tarjan 缩点，然后在 DAG 上 BFS …

强连通分量 题目：P3387 缩点 题目大意： 给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。 分析: 先使用 tarjan 缩点，然后对图进行重构，再对拓扑图记忆化搜索。 #include <b…