AcWing 846. 树的重心（dfs）-Toy模板网

这篇具有很好参考价值的文章主要介绍了AcWing 846. 树的重心（dfs）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

这是一道我一开始没怎么看懂的题目，然后后面看了y神的讲解就豁然开朗了

不过我们首先要有先置知识来理解这道题目

先置知识

邻接表：是一种表示图的数据结构，它通过链表的方式记录每个顶点及其相邻的顶点。在这个具体的问题中，使用数组 h 来表示邻接表。

h 数组：h 数组的每个元素 h[i] 是一个链表的头指针，指向以节点 i 为起点的链表的第一个元素。链表中的每个节点表示节点 i 可以直接连接的其他节点。

int h[N];
Arrays.fill(h, -1);

这段代码初始化了 h 数组，将每个顶点的链表头指针初始化为 -1，表示初始时每个顶点没有相邻的节点。

数组建立邻接表

int h[N], e[N * 2], ne[N * 2], idx;  // 数组范围要得是两倍才行
public static void add(int a, int b) {
    e[idx] = b;      // 将节点b添加到节点a的邻接表中
    ne[idx] = h[a];   // 更新节点a的邻接表头，将当前边的下一个节点设置为原来的邻接表头
    h[a] = idx++;     // 更新节点a的邻接表头为当前边的索引，并将索引自增
}

e 数组存储了图中边的终点，ne 数组存储了下一条边的索引，h 数组存储了每个节点的邻接表头。
idx 是一个全局变量，用于表示当前边的索引。
在函数内部，首先将节点b添加到节点a的邻接表中（表示a指向b）。
然后，更新节点a的邻接表头，将当前边的下一个节点设置为原来的邻接表头。
最后，更新节点a的邻接表头为当前边的索引，并将索引自增，确保每次添加边都使用新的索引。

树的bfs模板

// 需要标记数组st[N],  遍历节点的每个相邻的便
void dfs(int u) {
    st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            dfs(j);
        }
    }
}

题目

给定一颗树，树中包含n个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式

输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

1≤n≤105文章来源地址https://www.toymoban.com/news/detail-787099.html

输入样例

输出样例：

代码与解析

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int N = 100010, M = N * 2;
    static int n;
    static int[] h = new int[N], e = new int[M], ne = new int[M];
    static int idx;
    static int ans = N;
    static boolean[] st = new boolean[N];

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

    // 深度优先搜索，返回以u为根的子树的节点数
    public static int dfs(int u) {
        st[u] = true;  // 标记节点u已经被访问
        int size = 0, sum = 0;  // size记录u的最大子树节点数，sum记录u统领的所有子节点数
        for (int i = h[u]; i != -1; i = ne[i]) {  // 遍历节点u的所有邻接节点
            int j = e[i];  // j为u的邻接节点
            if (st[j]) {  // 如果j已经被访问过，继续下一个邻接节点
                continue;
            }
            int s = dfs(j);  // 递归调用dfs，计算以j为根的子树的节点数
            size = Math.max(size, s);  // 更新u的最大子树节点数
            sum += s;  // 累加u统领的所有子节点数
        }
        size = Math.max(size, n - sum - 1);  // 计算删除u后，剩余各个连通块中节点数的最大值
        ans = Math.min(size, ans);  // 更新全局最小值
        return sum + 1;  // 返回u节点+所有u节点统领的节点的综合
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();  // 读取树的总节点数
        Arrays.fill(h, -1);  // 初始化每个节点的链表为空
        for (int i = 1; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a, b);  // 添加一条从a到b的边
            add(b, a);  // 添加一条从b到a的边
        }
        dfs(1);  // 从节点1开始深度优先搜索
        System.out.println(ans);  // 输出最终结果
    }
}