最も遠いノード

問題の説明

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 bfs(v, visited, adj):
    count = 0
    q = deque([[v, count]])
    while q:
        value = q.popleft()
        v = value[0]
        count = value[1]
        if visited[v] == -1:
            visited[v] = count
            count += 1
            for e in adj[v]:
                q.append([e, count])

def solution(n, edge):
    answer = 0
    visited = [-1] * (n + 1)
    adj = [[] for _ in range(n + 1)]
    for e in edge:
        x = e[0]
        y = e[1]
        adj[x].append(y)
        adj[y].append(x)
    bfs(1, visited, adj)
    for value in visited:
        if value == max(visited):
            answer += 1
    return answer