牛客网真题-81-图的遍历-美团MT44

开始写深度优先遍历一步步走，走一步+1，只能过40%，因为可能不是最长的最后走完
看了大佬说 2*（n-1）-最长，然后开始写了一个广搜。

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList[] arr = new ArrayList[n + 1];//邻接表
        for(int i = 1; i <arr.length ; i++){
            arr[i]=new ArrayList<Integer>();
        }
        int len = 0;
        for(int i = 0; i < n - 1; i++){
            int x = scanner.nextInt(), y = scanner.nextInt();
            arr[x].add(y);
            arr[y].add(x);
        }
        //广度优先遍历
        Stack<Integer> stack = new Stack<>();
        stack.add(1);
        int[] visited = new int[n + 1];
        visited[1] = 1;
        while (!stack.isEmpty()) {
            len++;
            Stack<Integer> stackT = new Stack<>(); //一层一层遍历搜索
            while (!stack.isEmpty()) {
                int now = stack.pop();
                ArrayList<Integer> arrayList = arr[now];
                for(Integer a : arrayList){
                    if(visited[a] == 0){//如果a没有被访问过
                        stackT.add(a);
                        visited[a] = 1;
                    }
                }
            }
            stack = stackT;
        }
        System.out.println(2 * (n - 1) - len+1);
    }
}