Overview

Given the friendship relationships among \(N\) students, find the “sum of friends’ numbers” for each student and output the maximum value.

Analysis

Understanding the Problem

The popularity of student \(i\) is the sum of the numbers of the students who are friends with student \(i\). Note that this is the “sum of numbers,” not the “number of friends.”

Example: When \(N = 4\), \(M = 3\) and the friendships are \((1, 3)\), \((1, 4)\), \((2, 4)\):

• Student \(1\)’s friends are \(3, 4\) → popularity = \(3 + 4 = 7\)
• Student \(2\)’s friend is \(4\) → popularity = \(4\)
• Student \(3\)’s friend is \(1\) → popularity = \(1\)
• Student \(4\)’s friends are \(1, 2\) → popularity = \(1 + 2 = 3\)

The maximum is \(7\).

Key Insight

Since friendships are bidirectional, when a relationship \((U_i, V_i)\) is given:

• Add \(V_i\) to student \(U_i\)’s popularity
• Add \(U_i\) to student \(V_i\)’s popularity

By performing this operation for each edge, we can compute the popularity of all students at once.

While it would also be correct to build an adjacency list and then sum up the friends’ numbers for each student, there is no need to create a list — simply adding directly each time an edge is read is sufficient.

Algorithm

1. Initialize an array popularity of size \(N+1\) with \(0\) (managed with 1-indexing)
2. Read the \(M\) edges sequentially, and for each edge \((U_i, V_i)\):
   • popularity[U_i] += V_i
   • popularity[V_i] += U_i
3. Output the maximum value among popularity[1] through popularity[N]

In this way, without explicitly building an adjacency list, we compute the popularity cumulatively while reading edges, which is both simple and efficient.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for array initialization, \(O(M)\) for processing the \(M\) edges, and \(O(N)\) for finding the maximum
• Space complexity: \(O(N)\)
  • Only the array to store popularity values

Implementation Notes

• Using a 1-indexed array (of size \(N+1\)) is convenient, as student numbers can be used directly as indices.

• When there are \(0\) friendships (\(M = 0\)), all students have a popularity of \(0\), but max(popularity[1:]) correctly returns \(0\).

• Using sys.stdin.readline speeds up input reading when \(M\) is large.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    popularity = [0] * (N + 1)
    for _ in range(M):
        u, v = map(int, input().split())
        popularity[u] += v
        popularity[v] += u
    print(max(popularity[1:]) if N >= 1 else 0)

main()

---

This editorial was generated by claude4.6opus-thinking.