概要

有向グラフ上で、特定のルールに従って全都市を巡回する順序をシミュレーションする問題です。各巡回では「重要度が最も大きい未調査の隣接都市」を貪欲に選び、行き先がなくなったら新たな巡回を開始します。

考察

問題の整理

手順を整理すると、次の2つの操作が交互に行われます：

1. 巡回の開始: 最初は都市 \(1\) から、2回目以降は未調査都市の中で重要度最大の都市から出発する。
2. 巡回中の移動: 現在の都市から出ている辺の先にある未調査都市のうち、重要度が最大のものに移動する。移動先がなければ巡回終了。

素朴なアプローチの問題点

各ステップで「未調査の隣接都市の中から重要度最大を探す」処理を愚直に行うと、毎回隣接リストを全走査する必要があります。最悪の場合、同じ辺を何度も確認することになり、\(O(N \times M)\) となって TLE の危険があります。

高速化のアイデア

隣接リストをあらかじめ重要度の降順にソートしておき、各頂点にポインタ（カーソル）を持たせます。ポインタは「次に確認すべき位置」を指しており、一度訪問済みと判定した要素は二度と見ません。これにより、全頂点の隣接リストの走査量の合計が \(O(M)\) に抑えられます。

アルゴリズム

1. 前処理: 各頂点の隣接リスト adj[u] を、隣接先の重要度 \(B[v]\) の降順にソートする。重要度から都市番号への逆引き配列 imp_to_city も作る。

2. 巡回の開始都市の管理: 全都市（都市 \(1\) 以外）を重要度の最大ヒープ（Pythonでは負値を使ったmin-heap）に入れておく。新しい巡回の開始時にヒープから取り出し、未調査であればその都市から出発する。

3. 巡回中の移動（ポインタ方式）:

   • 各頂点 \(u\) にポインタ ptr[u] を用意（初期値 \(0\)）。
   • 現在の都市 current の隣接リストを ptr[current] の位置から順に見る。
   • 訪問済みの都市はスキップして ptr[current] を進める。
   • 未調査の都市が見つかればそこに移動し、調査済みにする。
   • 見つからなければ巡回終了。

4. 全都市調査まで繰り返す。

具体例

都市が \(4\) つ、辺が \(1 \to 2, 1 \to 3, 2 \to 4\) で重要度が \(B = [3, 4, 1, 2]\)（都市1の重要度3、都市2の重要度4、…）の場合：

• 1回目の巡回: 都市 \(1\) から出発 → 隣接する未調査都市は \(\{2, 3\}\)、重要度は \(B[2]=4, B[3]=1\) なので都市 \(2\) へ → 都市 \(2\) の隣接未調査は \(\{4\}\) なので都市 \(4\) へ → 都市 \(4\) の隣接未調査なし → 巡回終了。調査順: \(1, 2, 4\)
• 2回目の巡回: 未調査で重要度最大は都市 \(3\)（重要度 \(1\)）→ 隣接未調査なし → 巡回終了。調査順: \(3\)
• 出力: 1 2 4 3

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 隣接リストのソート: \(O(M \log N)\)
  • ヒープ操作: \(O(N \log N)\)
  • ポインタによる隣接リスト走査: 各辺は高々1回しかスキップされないため合計 \(O(M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• ポインタ方式が核心: ptr[u] を使うことで、一度スキップした訪問済み頂点を再度確認しないようにしています。ソート済みリストの先頭側ほど重要度が高いので、ポインタを進めながら最初に見つかった未調査都市がそのまま重要度最大の候補です。

• 最大ヒープの代替: Pythonの heapq は最小ヒープなので、重要度の符号を反転して挿入（-B[i]）することで最大ヒープを実現しています。

• 1回目の巡回だけ特殊: 出発都市が「未調査で重要度最大」ではなく固定で都市 \(1\) である点に注意が必要です。フラグ first_tour で制御しています。

  ソースコード

import sys
from heapq import heappush, heappop

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    B = [0] * (N + 1)
    for i in range(1, N + 1):
        B[i] = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
    
    # For each city, sort neighbors by importance descending for efficient traversal
    # We'll use a max-heap (negate values) for neighbors
    
    visited = [False] * (N + 1)
    result = []
    
    # We need to efficiently find the unvisited city with max importance for new tours
    # Use a max-heap of all cities by importance
    # For the first tour, start city is 1
    # For subsequent tours, pick unvisited city with max importance
    
    # For adjacency, we need to pick unvisited neighbor with max importance
    # We can use a heap per node, but that's expensive
    # Instead, sort adjacency lists by importance descending, and use a heap during traversal
    
    # Sort adjacency lists by B[v] descending
    for u in range(N + 1):
        adj[u].sort(key=lambda v: -B[v])
    
    # Global heap for picking start cities (max-heap by importance)
    # We'll add all cities except city 1
    global_heap = []
    for i in range(1, N + 1):
        if i != 1:
            heappush(global_heap, -B[i])
    
    # Map from importance to city
    imp_to_city = [0] * (N + 1)
    for i in range(1, N + 1):
        imp_to_city[B[i]] = i
    
    # First tour starts at city 1
    first_tour = True
    start_city = 1
    
    while True:
        if first_tour:
            current = start_city
            first_tour = False
        else:
            # Find unvisited city with max importance
            current = -1
            while global_heap:
                neg_imp = heappop(global_heap)
                imp = -neg_imp
                city = imp_to_city[imp]
                if not visited[city]:
                    current = city
                    break
            if current == -1:
                break
        
        if visited[current]:
            # This shouldn't happen for first tour if city 1 is valid
            # For subsequent tours, we already checked
            continue
        
        # Start tour from current
        visited[current] = True
        result.append(current)
        
        # Use pointer-based approach for adjacency lists
        # For each node, maintain a pointer into its sorted adjacency list
        # But we need to skip visited nodes
        
        while True:
            # Find unvisited neighbor with max importance
            found = False
            best_neighbor = -1
            best_imp = -1
            
            for v in adj[current]:
                if not visited[v]:
                    if B[v] > best_imp:
                        best_imp = B[v]
                        best_neighbor = v
                        # Since sorted descending, first unvisited is the best
                        found = True
                        break
            
            if not found:
                break
            
            current = best_neighbor
            visited[current] = True
            result.append(current)
        
        if len(result) == N:
            break
    
    sys.stdout.write(' '.join(map(str, result)) + '\n')

# The above has worst case O(N*M) due to scanning adjacency lists
# Let's optimize with pointers into sorted adjacency lists

def main_optimized():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    B = [0] * (N + 1)
    for i in range(1, N + 1):
        B[i] = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
    
    for u in range(N + 1):
        adj[u].sort(key=lambda v: -B[v])
    
    imp_to_city = [0] * (N + 1)
    for i in range(1, N + 1):
        imp_to_city[B[i]] = i
    
    visited = [False] * (N + 1)
    ptr = [0] * (N + 1)  # pointer into adj[u]
    result = []
    
    global_heap = []
    for i in range(1, N + 1):
        if i != 1:
            heappush(global_heap, -B[i])
    
    first_tour = True
    
    while len(result) < N:
        if first_tour:
            current = 1
            first_tour = False
        else:
            current = -1
            while global_heap:
                imp = -heappop(global_heap)
                city = imp_to_city[imp]
                if not visited[city]:
                    current = city
                    break
            if current == -1:
                break
        
        if visited[current]:
            continue
        
        visited[current] = True
        result.append(current)
        
        while True:
            nxt = -1
            while ptr[current] < len(adj[current]):
                v = adj[current][ptr[current]]
                if not visited[v]:
                    nxt = v
                    break
                ptr[current] += 1
            
            if nxt == -1:
                break
            
            current = nxt
            visited[current] = True
            result.append(current)
    
    sys.stdout.write(' '.join(map(str, result)) + '\n')

main_optimized()

---

この解説は claude4.6opus-thinking によって生成されました。