\(O(N+M)\) 時間で解くことができます。

\(O((N+M) \log (N+M))\) 解法

まず、この問題は \(k\) について次のように解くことができます。

• 頂点 \(1\) から頂点番号 \(k\) 以下の頂点のみを辿って訪れることができる頂点の集合を \(S(k)\) とする。
• \(S(k) \ne \{1,2,\cdots, k\}\) なら、答えは -1 である。そうでないなら、 \(S(k)\) に隣接する頂点番号 \(k+1\) 以上の頂点の個数が答えになる。

これを \(k=1,2,\cdots,N\) の順に優先度付きキューなどを用いて都度求めることで \(O((N+M)\log(N+M))\) 時間で解けます。この解法を工夫して \(O(N+M)\) 時間で解くことができます。

\(O(N+M)\) 時間

上のアルゴリズムの性質を考えると、 \(k+1\) の計算で

• 頂点 \(k+1\) が \(S(k)\) に隣接しないなら \(S(k+1)=S(k)\) である。
• 頂点 \(k+1\) が \(S(k)\) に隣接するとき、\(k+1 \in S(k+1)\) である。このとき、 \(S(k+1) \backslash S(k)\)、すなわち新しく訪問することができる頂点は、頂点 \(k+1\) から頂点 \(k+1\) 以下の頂点のみを用いて訪れることができる頂点の集合である。

ここで、 \(S(k)\) に隣接する頂点の最小値を取得する必要はない（頂点 \(k+1\) が含まれているかどうかだけを判定すればよい）ため、優先度付きキューで管理する必要はありません。

\(S(k)\) に隣接する頂点を bool 型配列で管理することで、 \(O(N+M)\) 時間で解くことができます。

実装(C++) 実装(Python)