概要

友達関係（無向辺）が与えられたとき、各生徒について「友達の番号の総和」を計算し、その最大値を求める問題です。

考察

生徒 \(i\) の人気度は「\(i\) と友達である生徒の番号の合計」です。
つまり、各友達関係 \((u, v)\) は人気度に対して

• 生徒 \(u\) の人気度に \(+v\)
• 生徒 \(v\) の人気度に \(+u\)

という 2つの加算 を発生させます。

素朴に「生徒ごとに友達を探して合計する」方法を考えると、例えば各生徒 \(i\) について全ての関係を走査して友達を探すような実装になりがちで、これは \(O(NM)\) となり最大で \((2\times 10^5)^2\) で間に合いません。

そこで、友達関係を1本読むたびに、その場で両端の人気度へ加算していけば、全体を 1回の入力走査 で計算できます。

例：\(N=4\)、辺が \((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\)
最終的に \(s[1]=7, s[2]=3, s[3]=3, s[4]=1\) なので答えは \(7\) です。

アルゴリズム

1. 長さ \(N\) の配列 \(s\) を用意し、\(s[i]\) を生徒 \(i\) の人気度（合計値）として \(0\) で初期化する。
2. 各友達関係 \((u, v)\) について以下を行う：
   • \(s[u] \leftarrow s[u] + v\)
   • \(s[v] \leftarrow s[v] + u\)
3. 最後に \(\max_{1 \le i \le N} s[i]\) を出力する。

計算量

• 時間計算量: \(O(N + M)\)（加算は各辺につき2回、最後に最大値を取る）
• 空間計算量: \(O(N)\)（人気度配列）

実装のポイント

• 辺は無向なので、必ず「両端に加算」します（片方だけだとWA）。

• \(N, M \le 2\times 10^5\) なので、Pythonでは sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 配列を N+1 サイズにして 1-indexed のまま扱うと、入力の番号と対応が取りやすいです。

• 友達が一人もいない生徒の人気度は \(0\) のままなので、最大値計算では s[1:] を対象にします。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。