AcWing 846. 树的重心
原题链接
简单
dfs深度优先遍历
Java 代码
/*
h[i]: 表示值为i的元素所在的链表头
e[i]: 存储元素值
ne[i]:存储e[i]的next节点下标值
*/
import java.util.*;
public class Main{
public static int N = (int)1e5 + 10;
public static int[] h = new int[N];//邻接表存储树,有n个节点,需要n个队列头节点
//有向图的格式存储无向图,所以每个节点至多对应2n-2条边
public static int[] e = new int[N * 2];//存储元素
public static int[] ne = new int[N * 2];//存储列表的next值
public static int n,idx = 0;//idx:单链表指针,n:输入节点
public static boolean[] flag = new boolean[N];//打标记
public static int ans = N;//表示重心的所有的子树中,最大的子树的结点数目
public static void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0; i < N; i++){
h[i] = -1;
}
// 会输入n-1行数据,树不存在环,有n个节点的树,必定是n-1条边
for(int i = 0; i < n - 1; i++){
int a = sc.nextInt();
int b = sc.nextInt();
//无向图
add(a, b);
add(b, a);
}
int end = dfs(1);
System.out.println(ans);
}
//以u为根的子树中点的数量
public static int dfs(int u){
flag[u] = true;//标记u这个点已经搜过了
int sum = 1;//当前子树大小
int res = 0;//删掉某个节点之后,最大的连通节点数
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(!flag[j]){
int s = dfs(j);
res = Math.max(res, s);
sum += s;
}
}
res = Math.max(res, n - sum);
ans = Math.min(ans, res);
return sum;
}
}
求关注
哇哦