問題

$n$ 頂点 $m$ 辺の連結な無向グラフがあり、 $i$ 番目の辺は頂点 ${u}_{i}$ と頂点 ${v}_{i}$ を双方向に結ぶ。また、すべての頂点に整数が書かれてあり、頂点 $v$ には整数 ${a}_{v}$ が書かれている。

頂点 $1$ から頂点 $n$ への単純なパス（同じ頂点を複数回通らないパス）に対して、以下のように得点を定める。

パス上の頂点に書かれた整数を通った順に並べた数列を $s$ とする。
$s$ が広義単調増加になっていない場合、そのパスの得点は $0$ である。
そうでない場合、 $s$ に含まれる整数の種類数が得点となる。

頂点 $1$ から頂点 $n$ へのすべての単純なパスのうち、最も得点が高いものを求め、その得点を出力せよ。

入力

まず最初の1行目には、整数 $n, \, m$ が与えられる。

次の1行には、整数 ${a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n}$ が順に与えられる。

次の $m$ 行のうち $i$ 行目には、整数 ${u}_{i}, \, {v}_{i}$ が与えられる。

条件

実行時間制限: 2s
メモリ制限: 1024MB
$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} \lt {v}_{i} \leq n$
$({u}_{i}, \, {v}_{i}) \ne ({u}_{j}, \, {v}_{j}) \; (i \ne j)$

出力

得点の最大値を1行で出力すること。

解法

まず、頂点 $1$ から頂点 $n$ までを通るパスについて、集合 $s$ が広義単調増加となるようなパスに必ずなるように、「パスが頂点 $u$ と頂点 $v$ を結ぶとき、 ${a}_{u} \leq {a}_{v}$ であれば $u \rightarrow v$ の、 ${a}_{u} \geq {a}_{v}$ であれば $u \leftarrow v$ の有向辺をはる」ということを考えます。

ここで具体的に、以下のようなグラフと $a$ が与えられているとします。（これは、問題の入力例1のものになります。）

このとき、例えば頂点 $1$ と頂点 $2$ を結ぶパスについては、 ${a}_{1} \leq {a}_{2}$ であるので、頂点 $1$ から頂点 $2$ への有向辺として考えます。

この場合の状況では、与えられた無向グラフは以下のような有向グラフに変換することができます。

この例では、数列 $a$ の中に等しい値は存在しないので、頂点 $1$ から頂点 $5$ に進むためのパスのうち、通る頂点数の最大値を求める問題として言い換えることができます。

この値を求めるには、各頂点の入次数が $0$ である頂点を基に、それを繋ぐ辺を順番に消していくことで、各頂点までに通過する頂点数の最大値を求めていくことで達成できます。

現在考えている状況では、まず頂点 $1$ の入次数が $0$ なので、まず頂点 $1$ について着目します。

頂点 $1$ から繋がっているのは頂点 $2, \, 3$ なので、まずは頂点 $2$ へと繋がっている辺を削除します。このとき、頂点 $2$ への通過数としては、頂点 $1, \, 2$ の $2$ 個ということになります。

同様に、頂点 $1$ から頂点 $3$ への辺を削除します。このとき、頂点 $3$ への通過数としては、頂点 $1, \, 3$ の $2$ 個となります。

頂点 $1$ から繋がっている辺はこれ以上存在しないので、頂点 $1$ についてはこれ以降は考えません。

次に、入次数が $0$ となっている頂点は $2, \, 3$ なので、これらを順に見ていきます。

頂点 $2$ からは頂点 $5$ へと繋がっているので、この辺を削除します。このとき、頂点 $5$ への通過数としては、頂点2の通過数が $2$ なので、 $2 + 1 = 3$ ということになります。

このように、入次数が $0$ の頂点を順番に見ていき、辺を削除していき、最終的に辺が無くなったときの、頂点 $n$ の通過数にあたる値がこの問題の答えとなります。今回の例では、以下の図のような遷移になるため、答えは $4$ となります。

さて、この有向グラフについては、頂点 $u$ と頂点 $v$ に辺が貼られており、 ${a}_{u} = {a}_{v}$ のときについては双方向に辺が貼られていることになります。一方で、 ${a}_{u} \lt {a}_{v} \lt {a}_{w} \lt {a}_{u}$ となるような $u, \, v , \, w$ は存在しないので、3頂点以上のループはこのグラフには存在しません。

従って、この双方向に貼られている頂点同士についてどのように扱うかを次に考えます。

頂点 $u$ と頂点 $v$ に対して双方向に辺が貼られているとき、 ${a}_{u} = {a}_{v}$ であるので、集合 $s$ の中に ${a}_{u}, \, {a}_{v}$ が含まれていても、スコアは伸びません。

例えば、以下の図のようなグラフについて、左端の頂点から頂点Aへと辿り着くまでに通る頂点数について考えます。ただし、頂点Aと頂点Bは双方向に結ばれているため、頂点Bは通過する頂点数には含めないこととします。

このとき、上のルートを通る場合だと、通過する頂点数は自身も含めて $4$ 個となります。一方で、頂点Bを経由する下のルートを通る場合だと、通過する頂点数は $5$ 個となります。

従って、頂点Aへと辿り着くまでに通る頂点数の最大値は $5$ 個となります。

また、頂点Bについては、下のルートを通るときの $5$ 個が最大値となります。

以上の例から、「頂点 $u$ と頂点 $v$ に対して双方向に辺が貼られているとき、通過する頂点数の最大値は等しくなる」ということが言えます。このことから、双方向に貼られている頂点については、まとめて1つの頂点として扱えると言えます。

先程の例の場合だと、この変換をした後のグラフは以下の図のようになります。

さて、この問題では頂点 $1$ から頂点 $n$ までのパスについて考えるため、頂点 $1$ に辿り着く前に登場する頂点については答えに影響を及ぼしません。すなわち、通過する頂点数には含まれないことになります。

これについては、例えば以下のようなグラフが完成されているとします。

このグラフについて、以下の灰色になっている部分については、頂点 $1$ から頂点 $n$ へのパスには含まれないことになります。

従って、頂点 $1$ からのパスについて考える前に、頂点 $1$ を通らないような頂点をグラフから取り除くことにより、先程の頂点数を考える手法から答えを求めることができると言えます。

以上の手順をまとめると、

与えられた数列の値と無向グラフの辺から、有向グラフを作成する
- この際に、双方向に結ぶ辺が存在する場合については、その頂点を1つの頂点として扱う
頂点 $1$ ではない入次数 $0$ の頂点から順に、頂点 $1$ に関係のない頂点と辺をグラフから取り除く
頂点 $1$ から順番に、辺をグラフから取り除いていき、パス中の頂点に対して通過した頂点数を求めていく

という方法によって、頂点 $1$ から頂点 $n$ までの $s$ のスコアの最大値を求めることができます。

計算量については、辺を辿りながら考えていくことから、 $O(m)$ 程度がかかりますが、これは実行時間制限に十分間に合います。

ソースコード

まず、 Union-Findの要領から、2つの頂点を1つの頂点として扱う部分を以下のように実装しました。

ここで、 group[i] は初期状態では group[i] = i として扱い、頂点 $u$ と頂点 $v$ を同じとして扱うときに、group[u] = group[v] となるようにしています。

int group[int(2e5 + 5)];

// 頂点 u の所属する group の値を返す
int find_group(int u) {
  if (group[u] == u) {
    return u; // もし group[u] = u であれば、それが所属するグループなのでその値を返す
  } else {
    return find_group(group[u]); // もしそうでなければ、 group[u] の値が所属するグループの値を返す
  }
}

// 頂点 u と頂点 v の所属するグループを同じにする
void unite(int u, int v) {
  // まずは u と v の現時点で所属するグループを求める
  int gu = find_group(u), gv = find_group(v);
  if (gu > gv) {
    swap(gu, gv);
  }

  group[gv] = gu; // gv のグループを gu にする
  group[u] = gu; // u のグループを gu にする
  group[v] = gu; // v のグループを gu にする
  return;
}

以上の関数がある状態で、 main() 関数の中に答えを直接出力する部分を実装しました。

int n, m, a[int(2e5 + 5)];
Pii edge[int(2e5 + 5)]; // 与えられた頂点同士を保存する pair<int, int> の vector
vector<int> graph[int(2e5 + 5)]; // 後に作成する有向グラフ

int group[int(2e5 + 5)]; // 頂点 i が所属するグループを表す
int edge_count[int(2e5 + 5)]; // 頂点 i の入次数を表す
int dp[int(2e5 + 5)]; // dp[i] は頂点 1 から頂点 i までの最大スコアを表す

int main() {
  // 値の入力
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    group[i] = i;
  }

  // 辺の入力
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    edge[i] = {u, v}; // i 本目の辺として、 {u, v} のペアを保存する
    if (a[u] == a[v]) { // もし a[u] = a[v] ならば、unite() を用いて頂点を統合する
      unite(u, v);
    }
  }

  // 各頂点に対して、find_group() を用いて group の値を更新しておく
  for (int i = 1; i <= n; i++) {
    group[i] = find_group(i);
  }

  // group の値と edge の値を用いて、有向グラフを作成する
  for (int i = 1; i <= m; i++) {
    int u = edge[i].first, v = edge[i].second;

    // もしグループが同じならば、同じ頂点として扱っているので、辺を追加する必要はない
    if (group[u] == group[v]) {
      continue;
    }

    // a[group[u]] < a[group[v]] の形にしたいので、そうでないときは u, v を swap する
    if (a[group[u]] > a[group[v]]) {
      swap(u, v);
    }

    // group[u] から group[v] への有向辺を追加する
    graph[group[u]].push_back(group[v]);
    // group[v] の入次数を 1 増やす
    edge_count[group[v]]++;
  }

  // 探索する頂点を保存するためのキューを用意する
  queue<int> que;

  // 頂点 1 以外の入次数 0 の頂点をキューに保存する
  for (int i = 2; i <= n; i++) {
    if (i == group[i] && edge_count[i] == 0) {
      que.push(i);
    }
  }

  // 頂点 1 に関わらない辺と頂点を削除する
  while (!que.empty()) {
    int now = que.front();
    que.pop();

    for (int next : graph[now]) {
      edge_count[next]--; // 頂点 next の入次数を 1 減らす

      // もし入次数が 0 になり、頂点 next が 1 でないならば、キューにその頂点を追加する
      if (edge_count[next] == 0 && next != 1) {
        que.push(next);
      }
    }
  }

  // 頂点 1 の答えを 1 と設定して、キューに追加する
  dp[1] = 1;
  que.push(1);

  // 頂点 1 からキューに入った順番に、辺の削除を行っていく
  while (!que.empty()) {
    int now = que.front();
    que.pop();

    for (int next : graph[now]) {
      edge_count[next]--; // 頂点 next の入次数を 1 減らす
      dp[next] = max(dp[next], dp[now] + 1); // 次の頂点の答えの値を更新する

      if (edge_count[next] == 0) {
        que.push(next); // 入次数が 0 になったら、キューにその頂点を追加する
      }
    }
  }

  // グラフは group[i] での値を頂点として扱っているため、頂点 group[n] での値を出力する
  cout << dp[group[n]] << endl;

  return 0;
}