题解 | 图的遍历

BFS搜索解法：

import sys
from typing import List, Dict
from collections import deque  # 添加导入

sys.setrecursionlimit(1 << 25)

class State:
    def __init__(self, node, weight):
        # 当前节点 ID
        self.node = node
        # 从起点 s 到当前节点的权重和
        self.weight = weight

class Edge:
    def __init__(self, to: int, weight: int):
        self.to = to
        self.weight = weight

def bfs(graph: Dict[int, List[Edge]], start: int):
    queue = deque([State(start,0)])  # 改用双端队列
    visited = [False] * (len(graph) + 1)  # 由于题目节点从1开始，我们就也从1开始吧，0索引位置当占位符
    visited[start] = True
    while queue:
        state = queue.popleft()
        cur = state.node
        weight = state.weight
        for neighbor in graph[cur]:
            if not visited[neighbor.to]:
                queue.append(State(neighbor.to,weight+neighbor.weight))
                visited[neighbor.to] = True
    return state.weight


N = 0
input = []
for line in sys.stdin:
    a = line.strip().split()
    if len(a) == 1:
        N = int(a[0])
    if len(a) == 2:
        input.append([int(a[0]), int(a[1])])

# 构建邻接表graph   {"节点val":[Edge,Edge,...]}
graph = {i: [] for i in range(1, N + 1)}
for edge in input:
    i = edge[0]
    j = edge[1]
    graph[i].append(Edge(j,1))
    graph[j].append(Edge(i,1))

print(2*len(input)-bfs(graph, 1))