Educational Codeforces Round 100 E.Plan of Lectures 缩点+拓扑排序
2022-07-12 17:14 作者:Asunataisiki | 我要投稿
题意:有一个人要讲门课,但是每门课
之后才能讲,若
,则没有需要提前讲的,并且现在还有
个条件,每个条件给出
和
,表示
之后的一门课必须是
,保证
且
, 问
门课的顺序是否有解
思路:条件一相当于给了我们一棵树,注意条件二的限制条件,表明给出的关系一定是若干条链,并且要求相邻,那么这一条件我们就可以进行缩点,而答案显然在图上有着明显的先后顺序,那么我们在新图上跑一次拓扑排序便是答案了。
注意:无解的情况,新图中有环,条件二的顺序与条件一中树的顺序不同(如条件二要求 1 -> 3, 而条件一中是3 -> 1),条件二中产生了环
具体细节见代码注释