AtCoder Beginner Contest 016 C - 友達の友達
問題概要
M個の友達関係が与えられるので各人に対して「友達の友達」の人数を出力する。
解法
「友達の友達」の人数であって、友達の人数は含まないことに注意。自分は友達関係をグラフに持って、dijkstraで各人の頂点からの最短距離を求めることにより、その人からの最短距離が2なら(最短距離が1で友達の関係なので)友達の友達の人数を追加する方式で実装した。
問題概要
M個の友達関係が与えられるので各人に対して「友達の友達」の人数を出力する。
解法
「友達の友達」の人数であって、友達の人数は含まないことに注意。自分は友達関係をグラフに持って、dijkstraで各人の頂点からの最短距離を求めることにより、その人からの最短距離が2なら(最短距離が1で友達の関係なので)友達の友達の人数を追加する方式で実装した。