概要

与えられたルール（未調査かつ重要度最大の都市を優先）に従って有向グラフ上を探索し、すべての都市の訪問順序を求める問題です。

考察

問題文の通りに愚直なシミュレーションを行うと、以下の2つの操作で時間がかかってしまいます。

1. 移動先の決定：現在の都市から移動できる未調査の都市のうち、重要度が最大のものを探す操作
2. 出発都市の決定：2回目以降の巡回で、未調査の都市全体から重要度が最大の出発都市を探す操作

これらの操作を毎回行うと、最悪の場合 \(O(N^2)\) の時間がかかり、TLE（実行時間超過）になってしまいます。これを解決するためには、事前のソートが有効です。

• 1の対策：各都市の隣接リスト（直接移動できる都市のリスト）を、あらかじめ「移動先の重要度」の降順（大きい順）にソートしておきます。これにより、巡回時にはリストを前から順番に見て、最初に見つかった未調査の都市に移動するだけでよくなります。
• 2の対策：すべての都市を重要度の降順に並べたリストをあらかじめ作成しておきます。さらに「リストのどこまで探したか」を記録する変数（ポインタ）を用意することで、毎回最初から探し直す無駄を省き、全体を通して \(O(N)\) で出発都市を見つけることができます。

アルゴリズム

1. グラフの構築とソート 各都市から移動できる都市をまとめた隣接リストを作成します。その後、各都市の隣接リストを、移動先の重要度 \(B\) の降順にソートします。
2. 出発都市候補の準備 すべての都市番号 \(1, 2, \dots, N\) を、重要度 \(B\) の降順にソートしたリスト unvisited_order を作成します。
3. 巡回のシミュレーション
   • 1回目の巡回は都市 \(1\) から開始します。
   • 現在いる都市の隣接リストを前から順に確認し、未調査の都市があればそこへ移動して調査済みにします。移動できる未調査の都市がなくなるまでこれを繰り返します。
   • 巡回が終了したら、unvisited_order を前から確認し、まだ調査されていない都市を次の出発都市とします（このとき、確認用のインデックスはリセットせず、前回の位置から再開します）。
   • すべての都市が調査済みになるまで、上記の巡回を繰り返します。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • 隣接リストのソートに \(\sum O(d_i \log d_i) \le O(M \log M)\) （\(d_i\) は各都市の出次数）、都市全体のソートに \(O(N \log N)\) かかります。シミュレーション部分は、各都市がちょうど1回ずつ現在の都市になり、各辺を最大1回しか確認しないため \(O(N + M)\) で完了します。全体として \(O(N \log N + M \log M)\) となり、十分に高速です。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストや、訪問済みを管理する配列などを保持するためのメモリが必要です。

実装のポイント

• 出発都市の探索インデックスを使い回す 2回目以降の出発都市を探すためのインデックス（コード内の unvisited_idx）は、巡回ごとに 0 にリセットせず、そのまま進め続けることが重要です。これにより、出発都市を探す while ループが全体で最大 \(N\) 回しか実行されなくなり、計算量を抑えることができます。

• ソートのキー（基準） 隣接リストや未訪問都市のリストをソートする際、都市番号そのものの大きさではなく、「都市の重要度 B[x]」をキーにして降順ソートするように注意しましょう。Pythonでは key=lambda x: B[x] のように指定することで簡潔に実装できます。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    
    B = [0] * (N + 1)
    for i in range(N):
        B[i + 1] = int(data[2 + i])
    
    adj = [[] for _ in range(N + 1)]
    idx = 2 + N
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx + 1])
        adj[u].append(v)
        idx += 2
        
    for i in range(1, N + 1):
        if len(adj[i]) > 1:
            adj[i].sort(key=lambda x: B[x], reverse=True)
            
    unvisited_order = sorted(range(1, N + 1), key=lambda x: B[x], reverse=True)
    
    visited = [False] * (N + 1)
    ans = []
    
    curr = 1
    while True:
        visited[curr] = True
        ans.append(curr)
        next_node = -1
        for nxt in adj[curr]:
            if not visited[nxt]:
                next_node = nxt
                break
        if next_node != -1:
            curr = next_node
        else:
            break
            
    unvisited_idx = 0
    while True:
        while unvisited_idx < N and visited[unvisited_order[unvisited_idx]]:
            unvisited_idx += 1
            
        if unvisited_idx == N:
            break
            
        curr = unvisited_order[unvisited_idx]
        while True:
            visited[curr] = True
            ans.append(curr)
            next_node = -1
            for nxt in adj[curr]:
                if not visited[nxt]:
                    next_node = nxt
                    break
            if next_node != -1:
                curr = next_node
            else:
                break

    print(" ".join(map(str, ans)))

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。