题目描述

算法1

Java 代码

import java.util.*;
import java.io.*;

public class Main {
    private static int n; // 一共的顶点数
    private static Map<Integer, List<Integer>> adj = new HashMap<>(); // 记录子节点(可能有多个)
    private static boolean[] v; // 是否访问过
    private static int ans; // 最终结果

    // DFS求当前的联通分量内点的个数，x是当前遍历到的点
    public static int dfs(int x) {
        int res = 0;
        int sum = 1;
        v[x] = true;
        List<Integer> list = adj.get(x); 
        for (int i = 0; i < list.size(); i++) {
            if (!v[list.get(i)]) {
                int s = dfs(list.get(i));
                res = Math.max(s, res);
                sum += s;
            }
        }
        res = Math.max(res, n - sum);
        ans = Math.min(ans, res);
        return sum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
        String s = b.readLine();
        n = Integer.parseInt(s);
        ans = n;
        v = new boolean[n+1];
        for(int i = 0; i < n-1; ++i){
            String[] edge = b.readLine().split("\\s+");
            int e1 = Integer.parseInt(edge[0]);
            int e2 = Integer.parseInt(edge[1]);
            if (!adj.containsKey(e1)) {
                adj.put(e1, new ArrayList<>());
            }
            adj.get(e1).add(e2);
            if (!adj.containsKey(e2)) {
                adj.put(e2, new ArrayList<>());
            }
            adj.get(e2).add(e1);
        }

        for (int i = 1; i <= n; i++){
            if(!v[i]){
                dfs(i);
            }
        }
        System.out.print(ans);
    }

}