ABC016 C - 友達の友達

問題

C: 友達の友達 - AtCoder Beginner Contest 016 | AtCoder

友達関係が与えられるので、各ユーザの「友達の友達」の人数を求めてください。ただし、自分自身や友達は、「友達の友達」に含みません。

解法

グラフの問題。

1. 入力から隣接リストを作る。
2. ユーザーiの各友達fに対して、その友達ffがiでもiの友達でもなければカウントする。

N, M = map(int, raw_input().split())
graph = [[] for i in xrange(N+1)]
for i in xrange(M):
    x, y = map(int, raw_input().split())
    graph[x].append(y)
    graph[y].append(x)

for i in xrange(1, N+1):
    num = 0
    done = [i]
    done.extend(graph[i])
    for f in graph[i]:
        for ff in graph[f]:
            if not ff in done:
                done.append(ff)
                num += 1
    print num

参考

Algorithms with Python / 集合, グラフ, 経路の探索