https://codeforces.com/contest/1876/problem/C
-
这次也差点想出来了 \(QwQ\)
-
遇到这种题第一感觉是建图。把 \(i \rightarrow a_i\) 得到一个 章鱼森林 (这里忘记了每个点只有一个出边,是章鱼森林)的黑白染色问题。要求:
-
不被圈的点的出边到达被圈的点
-
被圈的点的所有入边中有一个不被圈的点
-
-
因此直接跑园方树即可
-
复杂度 \(O(n)\)
https://codeforces.com/contest/1876/problem/C
这次也差点想出来了 \(QwQ\)
遇到这种题第一感觉是建图。把 \(i \rightarrow a_i\) 得到一个 章鱼森林 (这里忘记了每个点只有一个出边,是章鱼森林)的黑白染色问题。要求:
不被圈的点的出边到达被圈的点
被圈的点的所有入边中有一个不被圈的点
因此直接跑园方树即可
复杂度 \(O(n)\)