CF1463E Plan of Lectures 题解

紊莫 · 2024-01-06 14:15:57 · 题解

如果要有解，那么这 k 个关系一定组成了若干条链，否则无解，不妨把这些链缩成一个个代表点，可以使用并查集解决。

将原图中的关系变成一个关键点构成的 DAG，如果无法构成，宣布无解，之后进行拓扑排序，得到一个答案。

但是还没完，需要验证答案，假设存在点 u 和点 v在同一条链中，u 在 v 前面，但是 v 却是 u 的祖先，那么是不行的，我们不妨采用如下方法模拟“解锁”的过程。

lock[root]=1;
for(int i:ans){
    if(!lock[i])
        cout<<0,exit(0);
    for(auto j:G[i])
        lock[j]=1;
}

这一步假如放到前面去做很难判断祖先关系，不如在最后验证一次答案比较简单。

总结：这题思维量不太大，但是情况比较多，稍有漏判就会出错。

示例代码。