グラフ（友達関係）

問題

ある学校のクラスには N 人の生徒が在籍しており、1 から N までの番号が付けられています。

このクラスには M 個の友達関係があり、各 i(1≦i≦M) について、生徒 Ai と生徒 Bi が互いに友達です。

最も友達の多い生徒の番号を出力してください。

該当者が複数いる場合は、該当者をすべて出力してください。

解き方・ソースコード

この問題は、生徒を頂点、友達関係を辺に置き換えたグラフと見なして解いていきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#-------- 入力例１ ---------
N = 5           # 生徒数
edges = [(1, 3), (2, 4), (3, 4), (3, 5)]    # 友達関係
#---------------------------
# 友達の数を数える
friend = [0] * N
for a, b in edges:
    friend[a - 1] += 1
    friend[b - 1] += 1

mx = max(friend)
for f in friend:
    if f == mx:
        print(f'最も友達が多い生徒の番号は {ans + 1} です。')

[実行結果（入力例１）]

最も友達が多い生徒の番号は 3 です。

最も友達が多い生徒の番号を表示することができました。