Overview

This is a problem where you calculate the sum of friend numbers (popularity) for each student and find the maximum value.

Analysis

The “popularity” defined in the problem statement is the sum of friend numbers for each student. For example, if student 1 is friends with student 2 and student 3, then student 1’s popularity is 2+3=5. This can be solved by simply summing up all the numbers in each student’s friend list. In graph theory terms, this is a problem of finding the sum of adjacent vertex (friend) numbers for each vertex (student).

Algorithm

1. Build an adjacency list: Prepare a list indexed by each student number and register friendships bidirectionally.
2. Calculate popularity for each student: For each student i, compute the sum of all numbers contained in the adjacency list adj[i].
3. Find the maximum: Calculate the popularity of all students and output the maximum value.

Complexity

• Time complexity: \(O(N + M)\)
  • Building the adjacency list takes \(O(M)\)
  • Computing popularity for each student takes \(O(\sum_{i=1}^{N} \text{deg}(i)) = O(M)\)
• Space complexity: \(O(N + M)\)
  • Storing the adjacency list takes \(O(N + M)\)

Implementation Notes

• The adjacency list should be implemented as 1-indexed rather than 0-indexed (since student numbers start from 1)

• Consider the case where the input data is empty (M=0)

• Since it is guaranteed that each student’s friend list contains no duplicates, no special deduplication handling is needed

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    
    adj = [[] for _ in range(n+1)]
    
    index = 2
    for i in range(m):
        u = int(data[index])
        v = int(data[index+1])
        index += 2
        adj[u].append(v)
        adj[v].append(u)
    
    max_popularity = 0
    for i in range(1, n+1):
        popularity = sum(adj[i])
        if popularity > max_popularity:
            max_popularity = popularity
            
    print(max_popularity)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.