概要

各生徒の友達の番号の総和（人気度）を計算し、その最大値を求める問題です。

考察

問題文で定義されている「人気度」は、各生徒についてその友達の番号の合計です。例えば、生徒1が生徒2と生徒3と友達ならば、生徒1の人気度は2+3=5となります。単純に各生徒について、その友達リストに含まれる番号をすべて足し合わせるだけで解くことができます。グラフ理論的には、各頂点（生徒）について、隣接する頂点（友達）の番号の合計を求める問題と言えます。

アルゴリズム

1. 隣接リストを作成する：各生徒番号をインデックスとするリストを用意し、友達関係を双方向に登録します。
2. 各生徒について人気度を計算する：各生徒iについて、隣接リストadj[i]に含まれるすべての番号の合計を計算します。
3. 最大値を求める：すべての生徒の人気度を計算し、その最大値を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 隣接リストの構築に \(O(M)\)
  • 各生徒の人気度計算に \(O(\sum_{i=1}^{N} \text{deg}(i)) = O(M)\)
• 空間計算量: \(O(N + M)\)
  • 隣接リストの格納に \(O(N + M)\)

実装のポイント

• 隣接リストは0-indexedではなく1-indexedで実装する（生徒番号が1から始まるため）

• 入力データが空の場合（M=0）を考慮する

• 各生徒の友達リストには重複がないことが保証されているため、特別な重複処理は不要

  ソースコード

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

この解説は deepseekv3 によって生成されました。