1 条题解

  • 0
    @ 2026-11-15 22:43:22

    本题考察了DFS树的相关知识。

    20pts

    O(2n)O(2^n) 枚举所有情况。

    +20pts

    会发现树的情况下,所有边一定为桥,输出任意构造方案即可。

    +20pts

    会发现基环树的情况下,只需要把环上所有边定向后,变为环,剩下边任取即可。

    100pts

    以上两档部分分其实都在提醒我们从 (ai,bi)(a_i,b_i) 这张图的角度看问题。

    首先这个题目描述很像拆点,把每个点拆成入点和出点,每次操作就是给无向边定向。

    然后考虑这样一个做法:把 aia_i 和 bib_i 连上一条双向边,然后在这个 nn 个点 mm 条边的无向图上跑 dfs,如果不是返祖边,那么就向上定向,否则向下定向。

    证明一下这个做法的正确性。

    首先如果一条边 (u,v)(u,v) 在无向图上是桥,那么在原图上无论怎么连也都是桥。因为在原图上,只有这条边连接了 uu 和 vv 所在的连通块,所以它在原图上也一定是桥。

    然后这么跑 dfs 相当于建出了很多强连通分量,如果 u→vu→v 和 v→uv→u 各有一条路径,删一条边一定不会影响连通性。

    所以这样跑肯定是最小的。

    时间复杂度:O(n+m)O(n+m)。

    信息

    ID
    221
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者