AcWing 846. 树的重心
原题链接
简单
思路:
对于每个点进行枚举,求出每个点把自身删掉后,最大连通块的节点个数
如何求把自身删掉后,最大连通块的个数?
当把自身删除后,树就被分成了两个部分:上面、以及下面所有的子树(也就是每一个独立的连通块)
求每一个子树的节点个数,这个很容易,树的深搜可以顺带解决这一点
如何求上面部分的所有节点个数? -> (总个数 - 该节点的个数) ,其中该节点个数为所有子树节点数+1
下面所有子树的每一颗树节点数的最大值,与上面部分节点数的最大值,就为该节点的最大连通块的节点数
然后与ans求个最小即可
具体看视频的解读
import java.util.*;
public class Main {
static int n;
static int N = 100010;
static int M = N * 2;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static boolean[] st = new boolean[N];
static int idx = 0;
static int ans = N;
private static void add(int a, int b) { // a->b
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
// 该返回以节点编号为u的子树的节点个数(包含节点u)
private static int dfs(int u) {
st[u] = true;
int sum = 1, res = 0;
for (int i = h[u]; i != -1; i = ne[i]) { // 遍历所有边
int j = e[i]; // 取得节点编号
if (!st[j]) {
int s = dfs(j); // 节点j的节点总数
res = Math.max(res, s); // 每次求最大的子树
sum += s;
}
}
res = Math.max(res, n - sum); // 最大还可能是上面剩余的部分
ans = Math.min(res, ans); // 然后与答案求一个最小
return sum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int cnt = n; // 由于这里的n在dfs中还要用,因此用另一个变量处理输入的边
for (int i = 0; i < N; i++) h[i] = -1;
while (cnt-- > 1) {
int a = sc.nextInt();
int b = sc.nextInt();
add(a, b);
add(b, a);
}
dfs(1);
System.out.println(ans);
}
}