プログラマグラフィックLV 3

プログラマグラフィックLV 3
最遠ノード
問題の説明
n個のノードを含むグラフィック.各ノード番号は1からnです.1ノードに最も近いノード数を取得します.最遠ノードとは、最短経路に移動したときに幹線数が最も多いノードを指す.
ノード個数n、幹線情報を含む2次元配列頂点をパラメータとして指定する場合は、1番ノードに最も近いノード数を返す解関数を作成します.
せいげんじょうけん
ノード数nは2万個を超えない.
幹線は双方向で、全部で1本以上50000本以下の幹線があります.
頂点配列の各行[a,b]は、a番ノードとb番ノードの間に幹線があることを示す.
I/O例
n vertex return
6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3
I/O例説明
下図に示すように,1番ノードから最も遠いノードは4,5,6番ノードである.

コード#コード#

from collections import deque

def solution(n, edge):
    graph=[[] for _ in range(n+1)]
    
    distance=[-1]*(n+1)
    
    for a in edge:
        graph[a[0]].append(a[1])
        graph[a[1]].append(a[0])
        
    queue=deque([1])
    distance[1]=0
    
    while queue:
        now =queue.popleft()
        nodes= graph[now]
        
        for i in nodes:
            if distance[i]==-1:
                queue.append(i)
                distance[i]=distance[now]+1
                
    max_num=max(distance)
    
    answer=0
    
    for d in distance:
        if max_num==d: 
            answer+=1
    
    return answer

グラフを作るために、空の2階建てのグラフを作ります.次に、距離を計算するために、−1からなるn+1の長さの距離リストを作成する.
双方向なので、双方向グラフで表します.
キューを生成し、最初の1を入れます.そして、スタートなので1を0に初期化します.
1->2 distance[2]=1 queue=[2]
1->3 distance[3]=1 queue=[2,3]
2->4 distance[4]=2 queue=[3,4]
2->5 distance[5]=2 queue=[3,4,5]
3->6 distance[6]=2 queue=[4,5,6]
4 queue=[5,6]
5 queue=[6]
6
の最後の部分
次に、最も遠い値の個数を計算します.