Codeforces Round #772 (Div. 2) E 二分图染色+拓扑序

思路

根据题目描述，显然对于两辆存在关系的车：

• 不可相遇：两车应相反而行
• 一定相遇：两车应相对而行

可以发现，两种关系下，车的的方向一定不相同。那么我们可以构造一张二分图，然后对图进行 0 − 1 0-1 0−1染色判断合法性。

然后考虑排序问题，显然对于存在关系的车(设坐标为 x L , x R x_L, x_R xL​,xR​)：

• 不可相遇： x L > x R x_L > x_R xL​>xR​
• 一定相遇： x L < x R x_L < x_R xL​ a[i].v; g1add(a[i].u, a[i].v); } for(int i = 1; i