ヒント \(\rightarrow\) https://atcoder.jp/contests/arc176/editorial/9825

解説の都合上、\(N\) 頂点のグラフ \(G\) であって、各 \(i\) に対して頂点 \(A_i\) と頂点 \(B_i\) の間に重み \(C_i\) の辺を貼ったグラフを構築しておきます。

\(\max(P_{A_i},P_{B_i}) = C_i\) ならば \(P_{A_i},P_{B_i} \le C_i\) が必要です。これを利用して各 \(i\) に対して \(P_i \le X_i\) という条件を求めておきます。(頂点 \(i\) が \(G\) で孤立点ならば \(X_i = \infty\) とします。)

\(k = N,N-1,...,1\) の順に \(P_i = k\) となる \(i\) を決めていきます。その際、以下のような場合分けを行います。

• $C_i = k$ となる $i$ が $2$ 個以上あるとき
$P_j = k$ となる $j$ は $1$ 個しか取れないので全ての重み $k$ の辺がある頂点 $v$ を端点に持つ必要があります。ここで、その頂点 $v$ は存在するならば一意に定まることに注意してください。$v$ が存在しないか $X_v < k$ ならばこの時点で答えは $0$ です。そうでなければ $P_v = k$ とします。
• $C_i = k$ となる $i$ がちょうど $1$ 個のとき
その辺の端点のうち、$X_j \ge k$ であるものを選び $P_j = k$ とします。端点が共に条件を満たす場合はどちらを選んでも状況が変わらないので答えを $2$ 倍して片方を $P_j = k$ とすればよいです。両方条件を満たさない場合この時点で答えは $0$ です。
• $C_i = k$ となる $i$ が存在しないとき
$X_j \ge k$ でありまだ $P_j$ が決まっていない頂点から $1$ 個選び $P_j = k$ とします。そのような頂点がない場合この時点で答えは $0$ です。そのような頂点が複数ある場合、どれを選んでも状況が変わらないので答えに候補の個数をかけて適当な頂点で $P_j = k$ とすればよいです。

\(C_i = k\) を満たす \(i\) に対して \(k=C_i\) のステップではまだ \(P_{A_i},P_{B_i}\) は決まっていないことなどに注意すると上記によって得られる順列が条件を満たすこと、また全ての条件を満たす順列を網羅していることが確認できます。

上記を \(X_j \ge k\) かつ \(P_j\) がまだ決まっていない \(j\) の個数を管理しながら行うことによって \(\mathrm{O}(N + M)\) でこの問題を解くことが出来ます。

実装例