49189-最も遠いノード

😄 問題の説明

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

💻 Pythonコード

from collections import deque

def dfs(graph, v, visited, height):
    visited[v] = height
    queue = deque([v])
    while queue:
        cur = queue.popleft()
        for node in graph[cur]:
            if visited[node] == -1:
                queue.append(node)
                visited[node] = visited[cur] + 1

def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n + 1)]
    for i in edge:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
    visited = [-1] * (n + 1)

    h = 0
    dfs(graph, 1, visited, h)
    max_height = max(visited)
    answer = len([i for i in visited if i == max_height])

    return answer