Overview

Given friendship relationships (undirected edges), the problem asks you to calculate the “sum of friend numbers” for each student and find the maximum value.

Analysis

The popularity of student \(i\) is “the sum of the numbers of all students who are friends with \(i\).” In other words, each friendship relationship \((u, v)\) generates two additions to the popularity values:

• Add \(+v\) to the popularity of student \(u\)
• Add \(+u\) to the popularity of student \(v\)

A naive approach of “for each student, search through all relationships to find their friends and sum them up” would result in \(O(NM)\) time complexity, which at maximum is \((2\times 10^5)^2\) and would not run in time.

Instead, by adding to the popularity of both endpoints each time we read a friendship relationship, we can compute everything in a single pass over the input.

Example: \(N=4\), edges are \((1,3),(1,4),(2,3)\) - \((1,3)\): \(s[1]+=3, s[3]+=1\) - \((1,4)\): \(s[1]+=4, s[4]+=1\) - \((2,3)\): \(s[2]+=3, s[3]+=2\) The final result is \(s[1]=7, s[2]=3, s[3]=3, s[4]=1\), so the answer is \(7\).

Algorithm

1. Prepare an array \(s\) of length \(N\), initializing \(s[i]\) (the popularity of student \(i\)) to \(0\).
2. For each friendship relationship \((u, v)\), do the following:
   • \(s[u] \leftarrow s[u] + v\)
   • \(s[v] \leftarrow s[v] + u\)
3. Finally, output \(\max_{1 \le i \le N} s[i]\).

Complexity

• Time complexity: \(O(N + M)\) (two additions per edge, then taking the maximum at the end)
• Space complexity: \(O(N)\) (popularity array)

Implementation Notes

• Since the edges are undirected, you must add to both endpoints (adding to only one side will result in WA).

• Since \(N, M \le 2\times 10^5\), in Python using sys.stdin.buffer.read() to read all input at once is faster.

• Using an array of size N+1 and handling it as 1-indexed makes it easier to correspond with the input numbering.

• Students with no friends will have a popularity of \(0\), so when computing the maximum, target s[1:].

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    s = [0] * (N + 1)
    idx = 2
    for _ in range(M):
        u = data[idx]
        v = data[idx + 1]
        idx += 2
        s[u] += v
        s[v] += u
    print(max(s[1:]))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.