题解 | 图的遍历

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int maxDepth = 0;  // 记录最远叶子节点的深度

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int curr, int depth) {
    visited[curr] = true;
    
    bool isLeaf = true;
    for(int next : graph[curr]) {
        if(!visited[next]) {
            isLeaf = false;
            dfs(graph, visited, next, depth + 1);
        }
    }
    
    if(isLeaf) {
        maxDepth = max(maxDepth, depth);
    }
}

int main() {
    int n;
    cin >> n;
    
    // 构建邻接表
    vector<vector<int>> graph(n + 1);
    for(int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    
    // DFS找最远叶子节点
    vector<bool> visited(n + 1, false);
    dfs(graph, visited, 1, 0);
    
    // 计算结果
    cout << 2 * (n - 1) - maxDepth << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static int maxDepth = 0;  // 记录最远叶子节点的深度
    
    static void dfs(List<List<Integer>> graph, boolean[] visited, int curr, int depth) {
        visited[curr] = true;
        
        boolean isLeaf = true;
        for(int next : graph.get(curr)) {
            if(!visited[next]) {
                isLeaf = false;
                dfs(graph, visited, next, depth + 1);
            }
        }
        
        if(isLeaf) {
            maxDepth = Math.max(maxDepth, depth);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 构建邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int i = 0; i < n - 1; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
        
        // DFS找最远叶子节点
        boolean[] visited = new boolean[n + 1];
        dfs(graph, visited, 1, 0);
        
        // 计算结果
        System.out.println(2 * (n - 1) - maxDepth);
    }
}

from collections import deque

def bfs(graph, start, n):
    visited = [False] * (n + 1)
    depth = [0] * (n + 1)
    queue = deque([(start, 0)])  # (节点, 深度)
    visited[start] = True
    max_depth = 0
    
    while queue:
        curr, d = queue.popleft()
        max_depth = max(max_depth, d)
        
        for next_node in graph[curr]:
            if not visited[next_node]:
                visited[next_node] = True
                depth[next_node] = d + 1
                queue.append((next_node, d + 1))
    
    return max_depth

def solve():
    n = int(input())
    
    # 构建邻接表
    graph = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)
    
    # BFS找最远节点
    max_depth = bfs(graph, 1, n)
    
    # 计算结果
    print(2 * (n - 1) - max_depth)

if __name__ == "__main__":
    solve()