CF1142E

题意

洛谷

做法

搞出粉色边的DAG,称之为图(T)

令有三个集合(X,Y,Z)(X)中存放可能成为答案的点集,(Y)(X)中通过粉红边能到达的点集,(Z)(X)中通过绿边能到达的点集;(X,Y,Z)的定义均不是严格的,即不在X中的点未必不能成为答案,不在(Y)中的点未必不能在(X)中通过绿边的点集...(|Xcup Ycup Z|=n,Xcap Y=emptyset,Xcap Z=emptyset,Ycap Z=emptyset)
集合(X)初始化成(T)中度数为(0)的点集,(Y)初始化成(T)中度数不为(0)的点集

取出(u,vin X),查询((u,v))的方向
(ulongrightarrow v):将(v)放入(Z),弹出(X);将(v)从图(T)中删去;将(v)出边度数为(0)的点(其实就是topsort的过程),放入(X),弹出(Y)
直到(X)中仅有一个元素

原文地址:https://www.cnblogs.com/Grice/p/12921738.html