自动搬运

查看原文

来自洛谷，原作者为

	henryhu2006 **

搬运于2025-08-24 22:48:38，当前版本为作者最后更新于2024-02-09 09:01:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

要求构造一棵 $n$ 个节点的内向有根树，使得给定的 $m$ 条有向边被包含，且给定的 $k$ 条有向边不被包含；或报告无解。

$n,m,k\le 3\times 10^5$。

包含

强制包含的边连上，得到一些弱连通块。

对于每个弱连通块必须满足下列条件，否则无解。

• 每个点出度最多为 $1$。
• 在对应的无向图中无环。
• 只有一个点出度为 $0$。

由此，每个弱连通块形成一棵有根子树，可以考虑将其缩成一个点，将不包含边也一起缩掉，边数不增；构造时需要注意指向该点的边只要任意对应其中一个点（在合法情况下），但从该点出发的边必须出发自根。

于是此题就转化为 $m=0$ 的情况。

判定根

枚举树的根。那么可以找出一个 DFS 树，能连接到的一定会被连接到。如果覆盖了全集，那么就找到答案；如果不存在这样一个根，则无解。

考虑具体实现，可以用一个哈希表 $h$ 来维护哪些点还没有被访问过，用 $n$ 个哈希表存和每个节点相关的不包含边。DFS 的时候枚举 $h$ 中所有元素并判断其是否在当前点的哈希表中存在，可以先枚举完再访问避免混乱。

分析复杂度，每次枚举要么找到一个子节点，要么枚举到一条不包含边。于是单次时间复杂度为 $\mathcal O(n+k)$，总复杂度为 $\mathcal O(n^2+nk)$。

有效根

判定过程已经没法优化了，可以从根入手。对于一个判定失败的根，其访问到的节点也已经尽可能扩展（子树中显然，其它横向、前向边对应的节点也访问完全），所以在这些点中不可能出现一个成功的根。

所以每次枚举根的时候选择没有访问的节点，如果其不能让剩下所有点被覆盖，那么它是失败的根。

所以只有最后一次完成覆盖的根能访问的那些点可能成为成功的根。如果只考虑最后一次的根，不考虑子节点等作为根，也是对的，因为其能覆盖剩下的所有点，同样可以利用上面的性质，如果它不行，它能访问的节点也不行。

最后还要清空，用已经确定的根再跑一遍判定。

每个点、边只被访问 $\mathcal O(1)$ 次，于是时间复杂度达到线性。

This solution idea can be seen as being inspired by Kosaraju’s algorithm for finding strongly connected components of a directed graph.（摘自官方题解）

没数据，于是没有代码。