题目描述
blablabla
样例
import java.util.*;
class Main{
static int[] h, ne, e;
static int idx;
static int min;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
init(n);
for (int i = 0; i < n - 1; i++) {
int a = sc.nextInt(), b = sc.nextInt();
add(a, b);
add(b, a);
}
min = n;
boolean[] visited = new boolean[n + 1];
dfs(1, visited, n);
System.out.println(min);
}
public static int dfs(int curNode, boolean[] visited, int n) {
visited[curNode] = true;
int ans = 0, sum = 1;
for (int nextIndex = h[curNode]; nextIndex != -1; nextIndex = ne[nextIndex]) {
int nextNode = e[nextIndex];
if (visited[nextNode]) continue;
int cur = dfs(nextNode, visited, n); // 所有下分枝的联通数量
sum += cur;
ans = Math.max(ans, cur); // 所有下分枝的最大联通
}
// 还要考虑上分枝的最大联通 n减去下分枝的总和再减去当前node
ans = Math.max(ans, n - sum);
// 得到的最大值来update res
if (ans < min) {
min = ans;
}
return sum;
}
public static void init(int n) {
h = new int[n + 1];
ne = new int[2 * n - 2];
e = new int[2 * n - 2];
Arrays.fill(h, -1);
}
public static void add(int a, int b) {
// h[a] 上放着所有边的idx 然后 最后一条边(idx)的下一个边的idx 是-1 一开始初始化h[a] = -1
// ne[idx] = h[a] h[a] = idx; 然后 e[idx] = b 这个边的另一点
ne[idx] = h[a];
h[a] = idx;
e[idx] = b;
idx++;
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla