問題文の指示通りに実装します。

出発都市を決める部分については、予め全ての都市を重要度順に並べた上で、各都市を調査済みかどうかを表すフラグを持ち、前回の出発都市の続きから都市を調べることで全体で \(O(N)\) で行うことができます。

擬似コード

visited = [False, ..., False]  # 調査済みかどうかを表す配列
sorted_town = [...]  # 重要度の降順に並べられた都市のリスト
pos = 0
while pos < N:
  next_town = sorted_town[pos]
  if visited[next_town] is False:
    start_at(next_town)  # next_town を出発都市として巡回を行う
  pos += 1

巡回を行う部分については、各都市から別の都市へ移動を試みる回数は高々 1 回であることから、「未訪問の都市のうち重要度が最大であるもの」を愚直に \(O(いまいる都市から伸びる道路の個数)\) かけて調べても、全体で \(O(M)\) になります。

以上より \(O(N+M)\) でこの問題を解くことができます。最初に都市 \(1\) から調査を行う必要があることに注意してください。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> b(n);
  for(int i=0; i<n; i++) cin >> b[i];
  vector<vector<int>> g(n);
  for(int i=0; i<m; i++){
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
  }

  vector<bool> visited(n);

  auto dfs = [&](auto self, int v) -> void{
    visited[v] = true;
    cout << v + 1 << endl;
    int next = -1, bmax = 0;
    for(auto vv: g[v]){
      if(!visited[vv] && b[vv] > bmax){
        next = vv;
        bmax = b[vv];
      }
    }
    if(next != -1){
      self(self, next);
    }
  };

  vector<pair<int, int>>bi(n);
  for(int i=0; i<n; i++){
    bi[i] = {b[i], i};
  }
  sort(bi.rbegin(), bi.rend());
  dfs(dfs, 0);
  for(auto[_, i]: bi){
    if(!visited[i]){
      dfs(dfs, i);
    }
  }
}

実装例 (Python)

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
B = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(M):
  U, V = map(int, input().split())
  U -= 1
  V -= 1
  G[U].append(V)

visited = [False] * N

def dfs(v):
  visited[v] = True
  print(v+1)
  Next = -1
  Bmax = 0
  for vv in G[v]:
    if not visited[vv] and B[vv] > Bmax:
      Next = vv
      Bmax = B[vv]
  if Next != -1:
    dfs(Next)

BI = [(b, i) for i, b in enumerate(B)]
BI.sort(reverse = True)
dfs(0)
for _, i in BI:
  if not visited[i]:
    dfs(i)