ABC478 E - lt and le

以下と未満

考え方

「未満」「以下」で区別するのではなく、「なるべく等しくしない」ことを考えてみる。
すると、この問題が言っていることは、ほぼ強連結成分分解そのものである。

よって、$u\to v$ の向きに辺を張った有向グラフを強連結成分分解すればよい。
そして、各番号の頂点が何番の成分に入ったかを整理する。
これで、全て「以下」なら必ず成立し、かつ可能な限り「未満」も成り立つようにしたものができる。

よって、これが条件を満たすかチェックすればよい。
満たすならこれがそのまま答え、満たさないならどうやっても不可能である。

AtCoder library の scc を使った場合、計算量は $O(N＋Q)$ である。

入力を受け取る。

各条件について、$u\to v$ の向きに辺を張る。

1 -> 4
2 -> 6
3 -> 2
3 -> 5
4 -> 1
4 -> 3
5 -> 7
6 -> 7

この有向グラフを強連結成分分解すると、次のように分けられる。

各頂点に、その頂点が入っている成分番号を割り当てる。

A: {1, 4, 2, 1, 3, 5, 6}

未満 の条件は $3\to5$ と $5\to7$ である。
それぞれ $A_3=2<A_5=3$、$A_5=3<A_7=6$ となっているので条件を満たす。

したがって、次のように出力できる。

Yes
1 4 2 1 3 5 6

特になし。

特になし。