AtCoder Beginnaer Contest 016 C – 友達の友達 をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginnaer Contest 016 C – 友達の友達

友達は友達の友達ではないので注意する。ややこしいな。
いろんな解き方・書き方があるので、いろいろ試してみるのも面白いかもしれない。
ここではsetを用いて、割とサボった書き方をしている。答えが通るならサボるのは美徳なので、これでいいのだ。

# AtCoder Beginnaer Contest 016 C - 友達の友達
# https://atcoder.jp/contests/abc016/tasks/abc016_3
# tag: グラフ 距離 高橋君

# 1 <= N <= 10 なので何も考えずに探索したあと、
# 自分自身と友達を除いて出力する方針で……

def main():
N, M = map(int, input().split())
relations = [list(map(int, input().split())) for _ in range(M)]

# 隣接リストでグラフ構築
friends = [[] for _ in range(N+1)]
for a, b in relations:
friends[a].append(b)
friends[b].append(a)

# 友達の友達、つまりグラフ上で 2 回移動する先を全て求める。
# 今回は制約も緩いので set でやってみることにしてみた。
# いろいろやり方はあると思うが、今回の制約ならかなり効率の
# 悪い判定でも、きちんと組めていれば十分間に合うだろう。
for i in range(1, N+1):
f_of_f = set()
for f in friends[i]:
f_of_f = f_of_f | set(friends[f])

# 自分自身と友達は引いて数える(集合演算)
excludes = {i} | set(friends[i])
print(len(f_of_f - excludes))

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です