自动搬运

查看原文

来自洛谷，原作者为

	Ametsuji_akiya AFO.

搬运于2025-08-24 21:41:07，当前版本为作者最后更新于2019-11-01 16:47:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

CAUTION！本篇目的在于纠正所有题解里的错误之处，可能有不妥之处，欢迎补充完善。

缩点。

第一问简单，求一下无入度点个数即可。

第二问简化后问题是给一张DAG求最少添加几条边使得DAG变成一个SCC。首先所有中间点（有入度有出度）肯定直接顺着走到无出度点，所以肯定是无出度点连向无入度点。

把无入度点作为点集S，把无出度点作为点集T。

二分图连边表示S点（入度为零）可以走到T点（出度为零），然后先暴力匹配，表示每一个$S_i$尽可能走一个互不相同的$T_i$点，然后所有匹配边从$T_i$向下一个匹配的$S_{i+1}$连一条边，表示从$S_i\to T_i\to S_{i+1}$，如此往复，最终将最后一个$T_k$连向开始时的$S_1$，此时形成一个环，是SCC。然后剩下的没被选上的是不连通的。如果是$S_i$点表明他所有可以走到的$T$都被其他$S$走过去了，$T$也是一样，能走到他的$S$都走到其他点$T$了，于是就把每一对未匹配的$T$向$S$连一下边，最后如果还剩下来就随便连了。这样，会发现左右两侧的点就都被连上了一条边。所以最少连边数量是$\max(|S|,|T|)$。如果要求方案的话就用这个二分图的匹配就行了，如果数据大了呢？再见

注意：上述证明结论的方法我翻阅了绝大部分网络题解，发现讲的都比较随便，都是“无出度点和无入度点随便两两匹配，直到每个点都有出度入度就是SCC了”。

错误在于：1.并不是随便选无出度点和无入度点的。hack！

n=4  m=3
1 3
1 2
4 3

2.并不是每个点都有入度和出度就是SCC了，可能是两个环通过一个有向边相连什么的。

所以我认为大部分题解的证明和构造答案方法都是错的。

当然我并没有就认为我的一定是对的。如果有谁可以推翻我的改正说法，欢迎爆踩指正。

代码什么的。。网上满天飞了。就不放了