[1] 有向グラフによる言い換え

\(i\) が \(j\) より弱くない（二者択一で選べる）ときに，\(i\to j\) に辺を張った有向グラフを考えます．次は同値です．

1. \(i\) が最後の一人になりうる．
2. \(i\) から全点に到達可能．

1 を仮定して 2 を示すには，二者択一で選ばれたという関係の辺のみを残せばよいです．他の人からは，誰に負けたかという関係を辿ると \(i\) に行きつくはずなので，これで \(i\) を根とする有向木（辺は根から出る向き）になります．

2 を仮定して 1 を示すには，\(i\) を根とする全域有向木をとって（例えば最短路木をとる），葉側から消していくようにすればよいです．

[2] 強連結成分分解との関係

一般の有向グラフで，「全点に到達可能」という条件を満たす頂点をすべて求めるには，次のようにすればよいです．

• 強連結成分に分解し，強連結成分のトポロジカル順をひとつとる．最初の成分の頂点をひとつとり，全点に到達可能であるか否かを調べる．到達不可能ならば解なし，到達可能ならばその成分の頂点をすべて出力する．

今回のグラフでは，（実はトポロジカル順は唯一で）最初の成分の頂点はすべて条件を満たします．問題設定からも「解が存在しない」ということはありえないということが分かると思います．

形式的には \(i\) を最初の成分の頂点，\(j\) をそれ以外の成分の頂点とすると，辺 \(j\to i\) は存在しないので，辺 \(i\to j\) が存在し，到達可能です．同じ成分の点にも当然到達可能です．

[3] 強連結成分分解の方法

結局，グラフを作って強連結成分分解すればよいです，が，定義通りにグラフを作ると計算量が大きいので上手く対処します．

この問題では「\(x_i \geq x_j\)」「\(y_i \geq y_j\)」「\(z_i \geq z_j\)」のいずれかが成り立つときに辺 \(i\to j\) を張ることになります．到達可能性を保つように辺を削減して辺を張ればよいので，これを使って辺を減らします．

適当にソートして，\(x_1\geq x_2\geq \cdots \geq x_n\) が成り立つとします．まず \(i\to i+1\) の形の辺をすべて張ります．これで \(x_i\) について大きい値から小さい値には到達可能になっています． 同じ値の到達可能性を保証するために，「\(x_L=\cdots=x_R\) ならば \(R\to L\) に辺を張る」というタイプの辺を追加します．

このような処理を \(x, y, z\) 成分それぞれで行えば，到達可能性を保った \(O(N)\) 本の辺のグラフを作れるので，これを強連結成分分解すればよいです．

[4] 参考

任意の \(i, j\)（\(i\neq j\)）に対して辺 \(i\to j\)，\(j\to i\) のちょうど一方が存在するようなグラフはトーナメントと呼ばれます．その強連結成分のトポロジカル順序は唯一です．本問では双方向に辺を張る点対が存在するのでトーナメントではありませんが，トーナメントに辺を追加したような構造をしており，やはり強連結成分のトポロジカル順序は唯一です．