题目描述
给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1 条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树
的重心。
算法
思路:遍历每个节点,求出每个节点重心值,以此反复
实现:dfs,在dfs的过程中,对每个节点计算结果
存储:树作为无向图存储在邻接表
具体代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
private static int N = 2 * 100010;
private static int idx = 0;
private static int[] h = new int[N];
private static int[] e = new int[N];
private static int[] ne = new int[N];
private static boolean[] st = new boolean[N];
private static int ans = Integer.MAX_VALUE;
private static int n = 0;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] line = reader.readLine().split(" ");
n = Integer.parseInt(line[0]);
Arrays.fill(h, -1);
for (int i=1; i<n; i++) {
line = reader.readLine().split(" ");
int n1 = Integer.parseInt(line[0]);
int n2 = Integer.parseInt(line[1]);
add(n1, n2); add(n2, n1);
}
dfs(2);
System.out.println(ans);
}
private static int dfs(int x) {
st[x] = true;
int size = 0; int sum = 1;
for (int i=h[x]; i!=-1; i=ne[i]) {
int j = e[i];
if (st[j]) continue;
int s = dfs(j);
size = Math.max(size, s); // 边走边遍历每个节点的重心值
sum += s;
}
size = Math.max(size, n - sum);
ans = Math.min(size, ans);
return sum; // if sum==1 -> 节点本身
}
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}