Overview

In a dance party, participants are paired in order from highest priority, where each participant selects the partner with the smallest number from their list of pair candidates. The problem asks us to find the partner of participant 1.

Analysis

To simulate the rules of the problem as described, we need to process participants in order from highest priority. By pre-sorting each participant’s pair candidates (the adjacency list of the graph) in numerical order, we can efficiently select the “partner with the smallest number” in step 3. Naively checking all candidates each time would take \(O(N^2)\) time in the worst case, but by pre-sorting the adjacency lists and only selecting unpaired partners, we can make this more efficient.

Algorithm

1. Read the input and represent the graph using adjacency lists. Sort each vertex’s adjacency list in numerical order.
2. Sort the participants in descending order of priority. This allows us to process them from highest to lowest priority.
3. For each participant, if they are still unpaired, iterate through their adjacency list in order and pair them with the first unpaired partner found.
4. After all pairs have been determined, output the partner of participant 1.

Complexity

• Time complexity: \(O(N \log N + M \log N)\)
  • Sorting by priority takes \(O(N \log N)\)
  • Sorting all adjacency lists of the graph takes \(O(M \log N)\) in total (letting \(d_i\) be the degree of each vertex, \(\sum d_i \log d_i \leq M \log N\))
  • The pairing process checks each edge at most once, so it takes \(O(M)\)
• Space complexity: \(O(N + M)\)
  • Storing the graph’s adjacency lists takes \(O(M)\)
  • Various flags and arrays take \(O(N)\)

Implementation Details

• The graph is represented using defaultdict(list), and each vertex’s adjacency list is sorted in numerical order.

• To process participants in descending order of priority, create a list of (priority, participant number) pairs and sort it.

• A paired array manages whether each participant has been paired, ensuring only unpaired participants are selected as partners.

• The partner of participant 1 can be directly obtained via partner[1].

  Source Code

import sys
from collections import defaultdict

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    R = list(map(int, data[2:2+n]))
    edges = []
    index = 2 + n
    graph = defaultdict(list)
    for i in range(m):
        u = int(data[index]); v = int(data[index+1]); index += 2
        edges.append((u, v))
        graph[u].append(v)
        graph[v].append(u)
    
    for node in graph:
        graph[node].sort()
    
    priority_order = []
    for i in range(1, n+1):
        priority_order.append((R[i-1], i))
    priority_order.sort(reverse=True)
    
    paired = [False] * (n+1)
    partner = [0] * (n+1)
    
    for _, x in priority_order:
        if paired[x]:
            continue
        for y in graph[x]:
            if not paired[y]:
                partner[x] = y
                partner[y] = x
                paired[x] = True
                paired[y] = True
                break
                
    print(partner[1])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.