自动搬运

查看原文

来自洛谷，原作者为

	chenzhiyuAndy **

搬运于2025-08-24 22:55:18，当前版本为作者最后更新于2025-03-02 23:50:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

给定 $n$ 个点 $m$ 条边的有向图，满足边看成无向边后图是森林，增加若干点和有向边，使得每个点出度都是完全平方数，且边看成无向边后图是一棵树。（$1 \le m < n \le 10^5$）

思路

首先考虑使森林联通，定义一个合法的连通块是其中没有出度不为平方数的点的连通块。随便找一个连通块 $p$，对于所有不合法的连通块，在其中找到一个不合法点向 $p$ 连接，这样显然更优，因为可能可以消除一些不合法点。然后最多剩下一个不合法连通块，现在要将它与其他合法连通块合并。若有一个不合法连通块，从其中的不合法点向其余连通块连边；若一开始就没有或在合并过程中所有连通块都变得合法，可以发现每个连通块都有一个出度为 $0$ 的点（因为没有就构成了环）从该点向其他连通块连边。这样的话便只剩下一个连通块，新建点使其合法即可。

代码

你觉得我会这么良心吗？本来不想贴的。但是... 所以为了估值...