Solution

• 对于 \(DAG\)，拓扑排序 \(+\) 倍增 \(LCA\) 就可以做了（不会的可以先做 [ZJOI2012] 灾难）
• 对于一般有向图（假设连通），转成等价的 \(DAG\) 后采用上述方法即可
• 首先构造出一棵 \(dfs\) 树，记录每个点的 \(dfn\)
• 显然一条边 \((u,v)\) 如果不在 \(dfs\) 树上，那么 \(dfn[u]>dfn[v]\)
• 然后定义 \(x\) 的半支配点 \(s[x]\)：
  \((1)\).如果存在任意一条路径 \((y,x)\)，使得这条路径上每个除 \(x,y\) 之外的点 \(z\) 都满足 \(dfn[z]>dfn[x]\)，那么称 \(y\) 是合法的
  \((2)\).在所有合法的 \(y\) 中找一个 \(dfn\) 最小的，就是 \(s[x]\)
• 将所有 \(s[x]\) 向 \(x\) 连边，再加上 \(dfs\) 树，就组成了一个等价的 \(DAG\)
• 考虑这样为什么是对的
  \((1)\).\(s[x]\) 一定是 \(x\) 在 \(dfs\) 树上的祖先，因此新图无环
  \((2)\).\(s[x]\) 到 \(x\) 一定有至少两条边不相交的路径
  \((3)\).\(s[x]\) 还是所有合法点在 \(dfs\) 树上的祖先，因为 \(dfn\) 最小
• 注意 \(s[x]\) 不一定支配 \(x\)，如果不存在合法点，那么 \(s[x]\) 为 \(dfs\) 树上的父亲
• 有什么不懂的画个图即可理解
• 考虑怎么求 \(s[x]\)，按 \(dfn\) 降序枚举 \(v\)，然后枚举边 \((u,v)\)
• 维护并查集，记录 \(v\) 已经枚举过的祖先中，\(dfn\) 最小的那个，记为 \(mn[v]\)
• 每做完一个点 \(v\)，把 \(v\) 向 \(fa[v]\) 合并
• 根据 \(dfn[u]\) 和 \(dfn[v]\) 大小关系进行讨论

• 详见代码，还是那句话，有什么不懂的画个图即可理解

  Code

// 求半支配点部分
inline int find(int x)
{
    if (x == fa[x]) return x;
    int t = fa[x];
    fa[x] = find(fa[x]);
    if (dfn[s[mn[t]]] < dfn[s[mn[x]]]) mn[x] = mn[t];
    return fa[x];
}

inline void init()
{
    int i, j;
    for (i = 1; i <= n; i++) fa[i] = mn[i] = s[i] = i;
    for (i = id[0]; i >= 2; i--)
    {
        int v = id[i], len = h[v].size(), res = n;
        // res 为最小合法点的 dfn，id[res] 即 dfn 为 res 的点，即 s[x]
        for (j = 0; j < len; j++)
        {
            int u = h[v][j];
            if (!dfn[u]) continue; // 注意可能图不连通
            if (dfn[u] < dfn[v]) res = min(res, dfn[u]);
            else
            {
                find(u);
                res = min(res, dfn[s[mn[u]]]);
                // 用 u 的已做过的祖先的最小 dfn 更新 res
            }
        }
        s[v] = id[res];
        add(s[v], v);
        fa[v] = anc[v]; // anc[v] 为 v 的祖先，fa[v] 是并查集，带路径压缩
    }
}

• 由于拓扑排序 \(+\) 倍增 \(LCA\)，时间复杂度 \(O(n\log n + m)\)。