Java实现树的重心dfs

解题思路

• 1、使用链式向前星建立无向图，需要建立2次，a->b,b->a
• 2、使用2个变量，sum来存储当前以x为根的节点数，res来保存连通块的数
• 3、最后for循环结束，统计到当前邻接表的总个数
• 4、找出所有最大连通块中，节点数最小的那个作为ans

import java.util.*;

public class Main {
    private static int N = 100010;
    private static int[] e = new int[2 * N];
    private static int[] ne = new int[2 * N];
    private static int[] h = new int[N];
    private static int idx = 0;
    private static boolean[] st = new boolean[N];

    private static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    private static int ans = N;
    private static int dfs(int x, int n) {
        int sum = 1; // 存储以x为root的树节点数，包含x节点自己
        int res = 0; // 存储删掉某个节点后，最大的连通子图节点数
        st[x] = true;
        for (int i = h[x]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                int s = dfs(j, n);
                res = Math.max(res, s); // 记录最大连通子图的节点数
                sum += s; // 累计计算以j为根的树的节点数
            }  
        }
        // n - sum为图中不包含根x的节点，也就是剩余部分的节点
        res = Math.max(res, n - sum);
        ans = Math.min(ans, res); // 结果保存，每次最大连通子图中，最小的节点数
        return sum; // 返回当前以x为根的这颗树的所有节点
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a, b);
            add(b, a);
        }
        dfs(1, n);
        System.out.println(ans);
        sc.close();
    }
}