P2272 [ZJOI2007] 最大半连通子图
注意到半联通子图缩完点一定是一条链，由于要求的是最大的半联通子图，所以该子图的每个强连通分量一定对应原图的完整的强连通分量，否则可以扩展。
则对原图缩点，最大半联通子图一定是从入度为 0 的点到出度为 0 的点的一条链，拓扑求出带权最长路即为第一问答案。
对于第二问，则考虑删去对最长路没有贡献的转移边，然后再对新图跑一遍拓扑排序求出方案即可。
标签：原图,连通,ZJOI,子图,联通,杂题 From： https://www.cnblogs.com/ORzyzRO/p/17965974