526互联

CF1876C Autosynthesis 题解

发布时间 2024-01-11 20:49:52作者: FOX_konata

Autosynthesis - 洛谷

https://codeforces.com/contest/1876/problem/C

  • 这次也差点想出来了 \(QwQ\)

  • 遇到这种题第一感觉是建图。把 \(i \rightarrow a_i\) 得到一个 章鱼森林 （这里忘记了每个点只有一个出边，是章鱼森林）的黑白染色问题。要求：

    • 不被圈的点的出边到达被圈的点

    • 被圈的点的所有入边中有一个不被圈的点

  • 因此直接跑园方树即可

  • 复杂度 \(O(n)\)