一、题目
点此看题
这题就不要看洛谷的翻译了，不按原题目翻译真的很不负责任。
有 \(1\sim n\) 的排列 \(p,q\)，现在给出 \(m\) 对关系 \((x_i,y_i)\)，表示 \((p_{x_i}-p_{y_i})(q_{x_i}-q_{y_i})\geq 0\)，现在要求您构造出排列 \(p,q\)，并使得满足 \(p_i\not=q_i\) 的位置 \(i\) 个数最大。
\(n\leq 5\cdot 10^5\)
二、解法
首先考虑答案上界，我们把关系当成边，明显度数为 \(n-1\) 的点必须满足 \(p_i=q_i\)（偏序关系被限制死了），设这样点的个数为 \(cnt\)，那么答案上界是 \(n-cnt\)
再从特殊情况开始考虑，比如有一个点和其他点完全没有限制，那么是可以把答案构造到 \(n\) 的，\(p,q\) 可以分别构造成：2,3,4...1...n-1,n、1,2,3...n...n-2,n-1，也就是把那个没有限制的位置分别填上最小值和最大值，其它点按位置顺序从小到大填就可以让每个位置都错开，并且两者的偏序关系一定是一致的。
回到原问题，我们可以将问题转化成：将所有位置分成若干组（不一定连续），每一组的大小大于 \(1\)，并且每组中含有和组内其它位置都没有任何限制的位置，然后给每组分配一段连续的标号。这样做的话组内可以构造达到最优，并且由于每组编号连续，所以组间的偏序关系相同，那么我们不需要考虑组间的限制。
问题就是如何分组了，可以从图论的角度考虑这个问题。我们把没有限制的点连边，那么一组在图上就是一个菊花的形式，菊花的中心就是那个组内没有限制的位置。我们只要把每个点都划分到一个大小 \(\geq 2\) 的菊花即可。
取原图的一个生成森林，对于每一棵树，我们自底向上构造菊花，叶子可以和它的父亲形成菊花，然后把叶子删去。如果和儿子形成了菊花的点也删去，如果最后还剩下根那么分配给任何一个儿子即可。
最后说一下实现的细节，取生成森林可以用 \(\tt set\) 暴力访问还没有被访问的点，由于每个点在 \(\tt dfs\) 最多只会跳过原有关系个数的点不去访问，所以时间复杂度 \(O(n\log n)\)，我们每次用 \(\tt upper\_bound\) 取下一个点可以避免一些奇怪的问题。
#include
#include
#include