缩完之后合法顺序变少了
把上一节那张有环的图缩点：每个强连通分量捏成一个点，分量之间的边保留（去掉重边和自环）。 n01 里那张 DAG 有 4 种合法顺序。缩点之后的这张图有几种？两个数一起输出： #include <algorithm> #incl
自己写：把缩点后的图建出来
把上一节那张有环的图缩点：每个强连通分量捏成一个点，分量之间的边保留（去掉重边和自环）。 comp[u] 已经算好了。建出缩点后的边集 ce，输出去重后的边数和 ce 的长度——两个数应该一样。 （本题用 g++ -std=c++17 -O
自己写：缩点后最长的链
把上一节那张有环的图缩点：每个强连通分量捏成一个点，分量之间的边保留（去掉重边和自环）。 缩完是一张 DAG，可以放心求最长链了。补全 longest，输出最长的一条链经过几个分量。 （本题用 g++ -std=c++17 -O0 编译。）
从哪几个点出发走遍全图
把上一节那张有环的图缩点：每个强连通分量捏成一个点，分量之间的边保留（去掉重边和自环）。 缩点后如果入度为 0 的分量只有一个，那个分量里的点就能走到全图；有两个或更多就谁也走不遍。输出那几个点，没有就输出 没有。 （本题用 g++ -st
缩点前排不全缩点后排全
把上一节那张有环的图缩点：每个强连通分量捏成一个点，分量之间的边保留（去掉重边和自环）。 拿同一个 kahn，在原图和缩点后的图上各排一次，输出各自排出来的个数。 （本题用 g++ -std=c++17 -O0 编译。）
最大流卡在哪儿
一张管道网，从水源到出口每秒最多能过多少水，取决于【0】。
增广路是什么
第 1 步：数字是每根管子的容量 第 2 步：找到 S→A→T：最细是 2 第 3 步：灌 2：出口收到 2 第 4 步：再找 S→B→T：最细也是 2 第 5 步：再灌 2：一共 4 第 6 步：再也找不到路：最大流 4 S A B T
这张网每秒最多过多少水
一张管道网，0 号是水源、6 号是出口，cap[u][v] 是 u→v 这根管子每秒最多能过多少水。 运行下面这段程序： #include <algorithm> #include <climits> #includ
自己写：灌满一条增广路
一张管道网，0 号是水源、6 号是出口，cap[u][v] 是 u→v 这根管子每秒最多能过多少水。 找路那半已经写好了，b 是这条路上最细的一段。补上灌水这两步。外层的 for (round < 50) 是步数上限，防止没写完时死转
把卡住它的那一刀找出来
一张管道网，0 号是水源、6 号是出口，cap[u][v] 是 u→v 这根管子每秒最多能过多少水。 最大流跑完之后，残量图里从水源还走得到的点已经算进 side 了。把跨出 side 的那些原图管子收成割，输出最大流/割容量/割上有几条边