Java 数据结构版本
这道题我用了HashMap也就是哈希表,里面嵌套了一个List(链表)。也就是说用java已经有数据结构来实现这道题,而没用原始的数组来模拟这两种数据结构。属于偷懒的一种方法吧,仅供参考。下面是代码
import java.io.*;
import java.util.*;
public class Main {
static int n, ans;
static boolean[] visited;
static Map<Integer, List<Integer>> map = new HashMap<>();
public static void main(String[] arg) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
ans = n;
visited = new boolean[2*n];
for (int i = 0; i < n - 1; i++) {
String[] in = br.readLine().split(" ");
int a = Integer.parseInt(in[0]), b = Integer.parseInt(in[1]);
map.computeIfAbsent(a, x -> new ArrayList<>()).add(b);
map.computeIfAbsent(b, x -> new ArrayList<>()).add(a);
}
dfs(1);
System.out.print(ans);
}
static int dfs(int u) {
visited[u] = true;
int sum = 1, res = 0;
for (int i : map.getOrDefault(u, new ArrayList<>())) {
if (!visited[i]) {
int j = dfs(i);
res = Math.max(res, j);
sum += j;
}
}
res = Math.max(res, n - sum);
ans = Math.min(ans, res);
return sum;
}
}