P9469 solution

· · 题解

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

## 包含 强制包含的边连上，得到一些弱连通块。 对于每个弱连通块必须满足下列条件，否则无解。 - 每个点出度最多为 $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.（摘自官方题解） 没数据，于是没有代码。