グラフ(友達関係)

問題

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

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

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

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

解き方・ソースコード

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

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#-------- 入力例1 ---------
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} です。')

[実行結果(入力例1)]

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

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