树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
一、AcWing 846. 树的重心
1.1题目
1.2思路分析
题意：什么是树的重心？
树的重心是指，删除某个结点后剩下的最大连通子树的结点数目最小，如下图是根据样列生成的树，若删除结点1，则剩下三个子树最大的是中间那颗结点有4个，即剩下的最大连通子树的结点数目为4；若删除结点2，则剩下两个数目为1的子树和一个数目为6的子树，即剩下的最大连通子树的结点数目为6；若删除结点3，剩下一个数目为1的子树，和一个数目为7的子树，即剩下的最大连通子树的结点数目为7……枚举可得剩下的最小的最大连通子树的结点数目为4也就是说结点1是树的重心。另外注意题目要求答案是输出剩下的最小的最大连通子树的结点数目。
思路
深搜，算出每个结点被删除后剩下的最大连通子树的结点数目，输出最小值即可，那么问题就是怎么求一个结点被删除后的最大连通子树的结点数目，删除一个结点后，剩下的子树可以被分为两个部分，例如删除结点4：
蓝色部分是结点4的子树，红色部分我们暂时称为其他部门，因为我们知道树的总结点数n，只要能算出蓝色部分的数目s，那么其他部分的数目就是n-s。
1.3Ac代码
import java.io.*;
import java.util.Arrays;
public class Main {
static int N = 100010;
static int M=2*N; //n-1条无向边需要两倍空间来存储
static int[] h = new int[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
static boolean[] st = new boolean[N]; //记录节点是否被访问过，访问过则标记为true
static int[] e = new int[M]; //存储元素
static int[] ne = new int[M]; //存储列表的next值
static int n, idx; //题目所给的输入，n个节点以及单链表指针
static int ans=N; //表示重心的所有的子树中，最大的子树的结点数目
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
Arrays.fill(h,1,n+1,-1); //结点从1开始，开始时边为空，即h数组值为-1表示无出边
for (int i = 0; i < n-1; i++) {
String []s=br.readLine().split(" ");
int a=Integer.parseInt(s[0]);
int b=Integer.parseInt(s[1]);
add(a,b); add(b,a);
}
dfs(1);
System.out.println(ans);
}
private static int dfs(int u) {
st[u]=true;
int sum=1; //当前子树大小，包括自己故从1开始
int res=0; //删除该结点后每一个连通块大小的最大值
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]){
int s=dfs(j); //其儿子子树的大小
res=Math.max(res,s); //找出儿子子树中的最大值
sum+=s;
}
}
res=Math.max(res,n-sum);//每个结点dfs最终得出的这个res即为以该结点为重心，删除后各个连通块中点数的最大值
ans=Math.min(res,ans);
return sum;
}
private static void add(int a, int b) {
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
}二、AcWing 847. 图中点的层次
2.1题目
2.2思路分析
用 d数组保存1号节点到各个节点的距离。
用 st 数组标记各个节点有没有走到过。
从 1 号节点开始，广度优先遍历：
1 号节点入队列，d[1] 的值更新为 0。
如果队列非空，就取出队头，找到队头节点能到的所有节点。如果队头节点能到走到的节点没有标记过，就将节点的d值更新为队头的d值+1，然后入队。
重复步骤 2 直到队列为空。
这个时候，d数组中就存储了 1 号节点到各个节点的距离了。
图的存储：邻接表
用 h 数组保存各个节点能到的第一个节点的编号。开始时，h[i] 全部为 -1。
用 e 数组保存节点编号，ne 数组保存 e 数组对应位置的下一个节点所在的索引。
用 idx 保存下一个 e 数组中，可以放入节点位置的索引
插入边使用的头插法，例如插入：a->b。首先把b节点存入e数组，e[idx] = b。然后 b 节点的后继是h[a]，ne[idx] = h[a]。最后，a 的后继更新为 b 节点的编号，h[a] = idx，索引指向下一个可以存储节点的位置，idx ++ 。
2.3Ac代码
import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Map;
import java.util.Queue;
public class Main {
static int N = 100010;
static int[] h = new int[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
static boolean[] st = new boolean[N]; //记录节点是否被访问过，访问过则标记为true
static int[] d = new int[N]; //存储距离
static int[] e = new int[N]; //存储元素
static int[] ne = new int[N]; //存储列表的next值
static int n,m, idx; //题目所给的输入，n个节点以及单链表指针
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String []s=br.readLine().split(" ");
n=Integer.parseInt(s[0]); m=Integer.parseInt(s[1]);
Arrays.fill(h,-1);
for (int i = 0; i < m; i++) {
s=br.readLine().split(" ");
int a=Integer.parseInt(s[0]);
int b=Integer.parseInt(s[1]);
add(a,b);
}
bfs();
System.out.println(d[n]);
}
private static void bfs() {
Queue<Integer> q=new ArrayDeque<>();
Arrays.fill(d,-1);
q.add(1);
d[1]=0;
st[1]=true;
while (!q.isEmpty()){
int he=q.poll();
for(int i=h[he] ;i!=-1;i=ne[i]){
int t=e[i];
if(!st[t]){
d[t]=d[he]+1;
q.add(t);
st[t]=true;
}
}
}
}
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}