ABC016 C - 友達の友達
今回はこちら。
グラフ問題ですね。
個人的にはグラフ問題はだいぶ慣れてきた感があります。
問題概要としては、各頂点について、1つの頂点を経てたどりづける頂点がいくつあるかを求める問題です。
ただし、1つの頂点を経てたどり着ける頂点が自分自身、もしくは自分自身と隣接している頂点は除きます。
注意点としては、1つの頂点を経てたどれる頂点が重複して数えられてしまう場合がある点でしょうか。
その点を気を付ければ何とかなるかと思います。
n, m = map(int,input().split()) relation = [[] for i in range(n + 1)] for i in range(m): a, b = map(int, input().split()) relation[a].append(b) relation[b].append(a) for i in range(1, n + 1): friends = relation[i] f_f = set() for f in friends: for ff in relation[f]: #自分自身は友達の友達ではない if ff == i: continue #自分と友達であれば友達の友達ではない if ff in friends: continue #友達の友達を重複して数える場合があるためsetで保持する f_f.add(ff) print(len(f_f))