概要

各都市を「未調査の中で重要度最大を優先する」という規則で巡回していくとき、調査される都市番号の列をシミュレーションで求める問題です。重要度の大小関係を前処理で固定しておくことで、高速に実行できます。

考察

この問題で必要になる「最大」の選択は 2 種類あります。

1. 巡回中：都市 \(u\) から 1 本で行ける未調査都市のうち、重要度 \(B\) が最大の都市へ移動
   
2. 巡回の開始：2 回目以降、未調査都市のうち重要度 \(B\) が最大の都市から開始

素朴にやると困ること

• 巡回の開始都市を毎回「未調査から最大 \(B\) を全探索」で選ぶと、最悪で \(O(N)\) を巡回回数分繰り返し、合計 \(O(N^2)\) になって TLE します（\(N \le 2\times 10^5\)）。
• 巡回中の「隣接先から最大 \(B\)」も、毎回最大値を探す必要があります。ただしこちらは各都市につき 1 回しか“現在地”にならない（後述）ので、工夫すれば合計 \(O(M)\) 程度にできます。

重要な観察

• 重要度 \(B_i\) は 順列（全て異なる）なので、「重要度が大きい順の都市リスト」を一度作れば、開始都市の選択はそのリストを前から見て未調査を探すだけでよいです。
• 巡回は「未調査の都市にしか移動しない」ため、各都市は一度しか訪れない（調査済みになった都市に戻らない）。
  よって、各都市 \(u\) について「\(u\) から次にどこへ行くか」を探す処理も、都市 \(u\) が訪問されたその 1 回だけで済みます。

この2点により、「開始都市の最大選択」と「隣接先の最大選択」を前処理で高速化し、全体を間に合わせられます。

アルゴリズム

前処理

1. 重要度配列 \(B[i]\) を読む。
2. 重要度 \(b\) に対応する都市番号を inv[b] として逆引きできるようにする（\(B\) が順列なので可能）。
3. 各有向辺 \(u \to v\) を隣接リスト adj[u] に追加。
4. 各都市 \(u\) について、adj[u] を \(B[v]\) の降順にソートする。
   これにより「未調査のうち重要度最大の行き先」は、先頭から見て最初の未調査を取ればよい。

さらに、重要度の降順に都市を並べた配列 [ \text{order_by_B} = [\text{重要度 }N\text{ の都市}, \text{重要度 }N-1\text{ の都市}, \dots] ] を inv を使って作る。

巡回（tour）

tour(start) を次で実装します：

• cur = start から始める
• cur を調査済みにして出力列に追加
• adj[cur]（重要度降順）を前から見て、最初の「未調査」頂点 nxt を探す
  • 見つかれば cur = nxt として続行
  • 見つからなければ巡回終了

全体の流れ

1. まず tour(1) を実行（問題の規則通り）。
2. まだ未調査が残っている間：
   • order_by_B を先頭から見て、未調査の都市を探す（ポインタ pos を進めるだけ）
   • それを開始都市として tour(その都市) を実行

これで規則通りの調査順が得られます。

計算量

• 時間計算量:
  隣接リストのソートが \(\sum_u O(\deg(u)\log \deg(u)) \le O(M\log M)\)、
  シミュレーション部分は各都市を 1 回だけ処理し、各辺も高々 1 回程度なめるので合計 \(O(N+M)\)。
  よって全体で \(O(M\log M + N + M)\)（支配項は通常 \(O(M\log M)\)）。
• 空間計算量: \(O(N+M)\)（隣接リスト、訪問管理、補助配列）

実装のポイント

• 隣接リストを \(B\) の降順にソートしておくと、「最大の未調査隣接先」は先頭からの線形探索で取れます。

• 開始都市選びは、重要度降順配列 order_by_B とポインタ pos により、毎回の全探索を避けます（未調査を見つけるまで pos を進めるだけ）。

• 入力が大きいので、Python では sys.stdin.buffer.read() による高速入力が有効です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = 0
    N = data[it]; it += 1
    M = data[it]; it += 1

    B = [0] * (N + 1)
    inv = [0] * (N + 1)
    for i in range(1, N + 1):
        b = data[it]; it += 1
        B[i] = b
        inv[b] = i

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = data[it]; v = data[it + 1]; it += 2
        adj[u].append(v)

    key = B.__getitem__
    for u in range(1, N + 1):
        if adj[u]:
            adj[u].sort(key=key, reverse=True)

    order_by_B = [inv[r] for r in range(N, 0, -1)]
    pos = 0

    visited = [False] * (N + 1)
    out = []

    def tour(start: int):
        cur = start
        while True:
            visited[cur] = True
            out.append(cur)
            nxt = 0
            for v in adj[cur]:
                if not visited[v]:
                    nxt = v
                    break
            if nxt == 0:
                break
            cur = nxt

    tour(1)

    while len(out) < N:
        while pos < N and visited[order_by_B[pos]]:
            pos += 1
        tour(order_by_B[pos])

    sys.stdout.write(" ".join(map(str, out)))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。