FES---结论证明

· · 题解

首先不同 SCC 无关联是好证的，因为无后效性，可以不计后果地随便赋值。

对于单个 SCC 考虑选任意一个点u为 “基准” ，那么从该点出发到v，长度为len的路径相当于u和v的差值最多为len。他们之间的点也一定在这个[dis[u],dis[v]]区间内，所以答案的上界就是区间的大小。由于边权只有-1、0、1，所以区间内的数一定能被取遍，答案能达到上界。该说法在以u为路径起点时有效，当取SCC所有点时，就可证明答案为SCC内最长路 + 1。