Overview

This problem requires exploring a directed graph according to given rules (prioritizing unvisited cities with the highest importance) and determining the visit order of all cities.

Analysis

If we perform a naive simulation exactly as described in the problem statement, the following two operations become time-consuming:

1. Determining the next destination: Finding the unvisited city with the highest importance among those reachable from the current city.
2. Determining the starting city: In the 2nd and subsequent tours, finding the unvisited city with the highest importance from all remaining unvisited cities.

If we perform these operations each time, it takes \(O(N^2)\) time in the worst case, resulting in TLE (Time Limit Exceeded). To solve this, pre-sorting is effective.

• Solution for 1: Pre-sort each city’s adjacency list (the list of directly reachable cities) in descending order of the destination’s importance. This way, during the tour, we simply scan the list from the beginning and move to the first unvisited city we find.
• Solution for 2: Pre-create a list of all cities sorted in descending order of importance. Additionally, by maintaining a variable (pointer) that records “how far we’ve searched in the list,” we avoid the waste of searching from the beginning each time, and can find the starting city in \(O(N)\) total across all tours.

Algorithm

1. Graph Construction and Sorting Create an adjacency list summarizing the cities reachable from each city. Then, sort each city’s adjacency list in descending order of the destination’s importance \(B\).
2. Preparing Starting City Candidates Create a list unvisited_order containing all city numbers \(1, 2, \dots, N\) sorted in descending order of importance \(B\).
3. Tour Simulation
   • The first tour starts from city \(1\).
   • Check the current city’s adjacency list from the beginning in order. If there is an unvisited city, move there and mark it as visited. Repeat this until there are no more reachable unvisited cities.
   • When a tour ends, check unvisited_order from the front and use the first city that is still unvisited as the next starting city (the search index is not reset but resumes from the previous position).
   • Repeat the above tours until all cities have been visited.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Sorting the adjacency lists takes \(\sum O(d_i \log d_i) \le O(M \log M)\) (where \(d_i\) is the out-degree of each city), and sorting all cities takes \(O(N \log N)\). The simulation part completes in \(O(N + M)\) because each city becomes the current city exactly once and each edge is checked at most once. Overall, this is \(O(N \log N + M \log M)\), which is sufficiently fast.
• Space complexity: \(O(N + M)\)
  • Memory is needed to store the graph’s adjacency lists, the array managing visited status, etc.

Implementation Notes

• Reusing the search index for starting cities It is crucial that the index for finding the starting city of the 2nd and subsequent tours (unvisited_idx in the code) is not reset to 0 for each tour but continues advancing from where it left off. This ensures that the while loop for finding the starting city executes at most \(N\) times in total, keeping the complexity low.

• Sort key (criterion) When sorting the adjacency lists and the unvisited cities list, be careful to sort in descending order using “the city’s importance B[x]” as the key, not the city number itself. In Python, this can be concisely implemented by specifying key=lambda x: B[x].

  Source Code

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()

This editorial was generated by gemini-3.1-pro-thinking.