搜索与图论 - 树的重心
程序员文章站
2023-12-27 08:46:45
...
1、题目描述
给定一颗树,树中包含n个结点(编号1~n)和n-1条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
输入格式
第一行包含整数n,表示树的结点数。
接下来n-1行,每行包含两个整数a和b,表示点a和点b之间存在一条边。
输出格式
输出一个整数m,表示重心的所有的子树中最大的子树的结点数目。
数据范围
1≤n≤1051≤n≤105
输入样例
9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6
输出样例:
4
2、分析
树可以看作是无环、连通的图。
3、代码
import java.util.*;
import java.io.*;
public class Main{
static int N = 100010;
static int M = 2 * N;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx;
static int answer = Integer.MAX_VALUE;
static boolean[] visit = new boolean[N];
static int n;
//存储图 一条边:a -> b
static void store(int a,int b) {
e[idx] = b;
ne[idx] = h[a]; //idx表示当前使用到的结点的下标
h[a] = idx;
idx ++;
}
//求把结点u删除后,u的每条子树分支包含的结点数量和
static int dfs(int u) {
visit[u] = true;
int res = 0, sum = 1; //sum初始化包含当前被删除的1个结点
for(int i = h[u];i != -1;i = ne[i]) {
int val = e[i];
if(!visit[val]) {
int size = dfs(val);
res = Math.max(res, size);
sum += size;
}
}
res = Math.max(res, n - sum); // 保存将这个点删除后,剩余各个连通块中点数的最大值
answer = Math.min(answer, res);
return sum;
}
public static void main(String[] args){
Scanner in = new Scanner(new InputStreamReader(System.in));
n = in.nextInt();
//初始化
for(int i = 0;i < h.length;i ++) {
h[i] = -1;
}
for(int i = 0;i < n-1;i ++) {
int a = in.nextInt();
int b = in.nextInt();
store(a, b);
store(b, a);
}
dfs(1); //从第一个结点开始删
System.out.println(answer);
}
}