【DFS】树的重心

题目

846. 树的重心

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

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

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

输入格式

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

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

输出格式

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

数据范围

$1 \le n \le 10^5$

输入样例

输出样例：

解题

方法一：BFS

思路

现有一棵树：

我们把红色的节点删掉后会发现这棵树变成了四个连通图，蓝色部分的节点数最多，而我们要做的就是对于每个节点都尝试删掉，然后求出节点最多的连通块的节点数，并找出最小的一个。

我们发现删掉一个节点后该节点原来的子节点一定都会变成独立的连通块，若该节点有父节点，那么它的父节点也会变成一个独立的连通块，所以可以设计递归函数，使递归函数返回以当前节点为根节点的子树的节点数量。对于每个节点，递归求出它子节点下面所有节点数并维护一个最大子树节点数量(mx)，再把子树节点数总和加一就是以它为根节点子树的节点数(sum)，此时删掉它后其父节点所在连通块的节点数量就是树所有节点的数量减去 sum，把这个数量拿去和 mx 相比取一个较大的就是删除该节点后剩余各个连通块中点数的最大值。

对于所有节点都这么干一次，并维护一个最小的剩余各个连通块中点数的最大值(ans)即为答案。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;
bool vis[N];
int n, ans = N;

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

int dfs(int u) {
    vis[u] = true;
    int sum = 1, mx = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!vis[j]) {
            int sz = dfs(j);
            sum += sz;
            mx = max(mx, sz);
        }
    }
    mx = max(mx, n - sum);
    ans = min(ans, mx);
    return sum;
}

int main() {
    memset(h, -1, sizeof(h));
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    dfs(1);
    printf("%d\n", ans);
    
    return 0;
}

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

public class Main {
    static final int N = (int) 1e5 + 10, M = 2 * N;
    static int n, idx;
    static int[] nodes, vals = new int[M], nexts = new int[M];
    static boolean[] vis;
    static int ans = N;
    
    static void add(int p, int q) {
        vals[idx] = q;
        nexts[idx] = nodes[p];
        nodes[p] = idx++;
    }
    
    static int dfs(int u) {
        vis[u] = true;
        int sum = 1, sonMax = 0;
        for (int i = nodes[u]; i != -1; i = nexts[i]) {
            int son = vals[i];
            if (!vis[son]) {
                int sz = dfs(son);
                sonMax = Math.max(sonMax, sz);
                sum += sz;
            }
        }
        int max = Math.max(n - sum, sonMax);
        ans = Math.min(ans, max);
        return sum;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        nodes = new int[n + 1];
        vis = new boolean[n + 1];
        Arrays.fill(nodes, -1);
        for (int i = 1; i < n; ++i) {
            in.nextToken();
            int p = (int) in.nval;
            in.nextToken();
            int q = (int) in.nval;
            add(p, q);
            add(q, p);
        }
        dfs(1);
        System.out.println(ans);
    }
}

目录CONTENT

【DFS】树的重心

题目

解题

方法一：BFS

思路

代码

评论区