問題概要
$n$ 頂点 $m $ 辺からなる連結な単純無向グラフ $G = ( V, E )$ があり，$i$ 番目の辺は頂点 $V_i$ と $U_i$ を双方向に結んでいる．また，整数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ が与えられる．
頂点 $1$ から頂点 $n$ への単純パス*1 $P = \langle P_1 = 1, P_2, \dots, P_k = n \rangle$ のスコアを
- 数列 $S = \langle A_{ P_1 }, A_{ P_2 }, \dots, A_{ P_k } \rangle$ をとる．
- $S$ について
- $S$ が広義単調増加*2でないとき，$P$ のスコアは $0$ ．
- そうでないとき，$S$ に含まれる整数の種類数が $P$ のスコア．
で定める．
可能なパスの内，スコアが最大となるもののスコアはいくらか？
制約
- $2 \leq n \leq 2 \times 10^5$
- $n - 1 \leq m \leq 2 \times 10^5$
- $1 \leq A_i \leq 2 \times 10^5$
- $1 \leq U_i < V_i \leq n$
- $( U_i, V_i )$ は相異なる
解法
$0$ でないスコアを得られるパス $P$ は任意の有効な $i$ について $S_i \leq S_{ i + 1 }$ でなければならないので，隣接する 2 頂点 $u, v \in V$ であっても，$A_u > A_v$ であったら $u$ から $v$ への移動はできません．このことを利用すると $G$ を有向化することができます*3．有向化したグラフを $G' = ( V, E' )$ とします．
$S$ の単調性から $P$ には一方向性的な性質があって，これはちゃんと言うとトポロジカル順序に沿うということです．なので，トポロジカル順序の小さい方から順にスコアを求めていく DP を考えることができます．DP の状態は $$\mathit{ dp }[u] := \text{頂点 $u$ が末尾となるパスの最大スコア}$$ となります．「配る DP」を考えると，頂点 $u$ からの更新は $$\mathit{ dp }[v] \leftarrow \max\left( \mathit{ dp }[v], \mathit{ dp }[u] + \begin{cases}
1 & \text{($A_u < A_v$)} \\
0 & \text{($A_u = A_v$)}
\end{cases} \right) \quad \text{(ただし $( u, v ) \in E'$)}$$ です．
有効なパス $P$ がトポロジカル順序に沿うことから，$G'$ をトポロジカルソートすることで，上記 DP の更新順序を（ほぼ）得ることができます．実は「ひとつの強連結成分 $C$ に属する頂点間の順序はどうするの」という話がありますが，題意より $C$ 内を無限にぐるぐるできるので，適切にぐるぐるすれば $u \in C$ の $\mathit{ dp }[u]$ の値は全て同一の値 $\max\limits_{ v \in C } \mathit{ dp }[v]$ になります．よって，ひとつの強連結成分内部については前記値をとってきてそれで埋めることで更新できます．
全ての更新が終わったあと，$\mathit{ dp }[n]$ が答えです．
計算量について
上記 DP をするとき，強連結成分 $C$ 内を埋める処理は，
- 成分内の最大値を求める処理に $\Theta( |C| )$ 時間
- 埋める処理にも $\Theta( |C| )$ 時間
がかかります．これはグラフ全体について和をとると $\Theta( n )$ 時間です．
強連結成分外に出る辺についての更新は，始点として全ての頂点を試し，最悪の場合全ての辺を辿ることになるので，$O( n + m )$ 時間*4がかかります．
また，前処理としての強連結成分分解は $O( n + m )$ 時間で実行できます．
結局，全体でも $O( n + m )$ 時間となり，TL に間に合います．
コード
// 強連結成分分解 / Strongly Connected Component // O( |V| + |E| ) class StronglyConnectedComponents; // 中身省略 // connect( from, to ) // solve() : 連結成分の数が返る // componentNumbers() : 頂点番号→連結成分の番号 の表が返る // 連結成分の番号の大小は、トポロジカル順序の大小と一致 int main() { IN( int, N, M ); VI A( N ); cin >> A; VVI G( N ); StronglyConnectedComponents scc( N ); REP( M ) { IN( int, u, v ); --u, --v; if ( A[u] <= A[v] ) { G[u].PB( v ); scc.connect( u, v ); } if ( A[v] <= A[u] ) { G[v].PB( u ); scc.connect( v, u ); } } const int K = scc.solve(); const VI belongs_to = scc.componentNumbers(); VVI components( K ); REP( i, N ) { components[ belongs_to[i] ].PB( i ); } VI scores( N ); scores[0] = 1; FOR( comp, components ) { int ma = 0; FOR( u, comp ) { chmax( ma, scores[u] ); } if ( ma == 0 ) { continue; } FOR( u, comp ) { scores[u] = ma; } FOR( u, comp ) { FOR( v, G[u] ) { if ( A[u] < A[v] ) { chmax( scores[v], scores[u] + 1 ); } } } } cout << scores.back() << endl; return 0; }
