一、AcWing 846. 樹的重心

1.1題目

1.2思路分析

題意：什么是樹的重心？

樹的重心是指，刪除某個(gè)結(jié)點(diǎn)后剩下的最大連通子樹的結(jié)點(diǎn)數(shù)目最小，如下圖是根據(jù)樣列生成的樹，若刪除結(jié)點(diǎn)1，則剩下三個(gè)子樹最大的是中間那顆結(jié)點(diǎn)有4個(gè)，即剩下的最大連通子樹的結(jié)點(diǎn)數(shù)目為4；若刪除結(jié)點(diǎn)2，則剩下兩個(gè)數(shù)目為1的子樹和一個(gè)數(shù)目為6的子樹，即剩下的最大連通子樹的結(jié)點(diǎn)數(shù)目為6；若刪除結(jié)點(diǎn)3，剩下一個(gè)數(shù)目為1的子樹，和一個(gè)數(shù)目為7的子樹，即剩下的最大連通子樹的結(jié)點(diǎn)數(shù)目為7……枚舉可得剩下的最小的最大連通子樹的結(jié)點(diǎn)數(shù)目為4也就是說結(jié)點(diǎn)1是樹的重心。另外注意題目要求答案是輸出剩下的最小的最大連通子樹的結(jié)點(diǎn)數(shù)目。

思路

深搜，算出每個(gè)結(jié)點(diǎn)被刪除后剩下的最大連通子樹的結(jié)點(diǎn)數(shù)目，輸出最小值即可，那么問題就是怎么求一個(gè)結(jié)點(diǎn)被刪除后的最大連通子樹的結(jié)點(diǎn)數(shù)目，刪除一個(gè)結(jié)點(diǎn)后，剩下的子樹可以被分為兩個(gè)部分，例如刪除結(jié)點(diǎn)4：

藍(lán)色部分是結(jié)點(diǎn)4的子樹，紅色部分我們暫時(shí)稱為其他部門，因?yàn)槲覀冎罉涞目偨Y(jié)點(diǎn)數(shù)n，只要能算出藍(lán)色部分的數(shù)目s，那么其他部分的數(shù)目就是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條無向邊需要兩倍空間來存儲(chǔ)static int[] h = new int[N]; //鄰接表存儲(chǔ)樹，有n個(gè)節(jié)點(diǎn)，所以需要n個(gè)隊(duì)列頭節(jié)點(diǎn)static boolean[] st = new boolean[N]; //記錄節(jié)點(diǎn)是否被訪問過，訪問過則標(biāo)記為truestatic int[] e = new int[M]; //存儲(chǔ)元素static int[] ne = new int[M]; //存儲(chǔ)列表的next值static int n, idx; //題目所給的輸入，n個(gè)節(jié)點(diǎn)以及單鏈表指針static int ans=N;   //表示重心的所有的子樹中，最大的子樹的結(jié)點(diǎn)數(shù)目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);    //結(jié)點(diǎn)從1開始，開始時(shí)邊為空，即h數(shù)組值為-1表示無出邊f(xié)or (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;  //當(dāng)前子樹大小，包括自己故從1開始int res=0;  //刪除該結(jié)點(diǎn)后每一個(gè)連通塊大小的最大值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);//每個(gè)結(jié)點(diǎn)dfs最終得出的這個(gè)res即為以該結(jié)點(diǎn)為重心，刪除后各個(gè)連通塊中點(diǎn)數(shù)的最大值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. 圖中點(diǎn)的層次

2.1題目

2.2思路分析

用 d數(shù)組保存1號(hào)節(jié)點(diǎn)到各個(gè)節(jié)點(diǎn)的距離。

用 st 數(shù)組標(biāo)記各個(gè)節(jié)點(diǎn)有沒有走到過。

從 1 號(hào)節(jié)點(diǎn)開始，廣度優(yōu)先遍歷：

1 號(hào)節(jié)點(diǎn)入隊(duì)列，d[1] 的值更新為 0。

如果隊(duì)列非空，就取出隊(duì)頭，找到隊(duì)頭節(jié)點(diǎn)能到的所有節(jié)點(diǎn)。如果隊(duì)頭節(jié)點(diǎn)能到走到的節(jié)點(diǎn)沒有標(biāo)記過，就將節(jié)點(diǎn)的d值更新為隊(duì)頭的d值+1，然后入隊(duì)。

重復(fù)步驟 2 直到隊(duì)列為空。

這個(gè)時(shí)候，d數(shù)組中就存儲(chǔ)了 1 號(hào)節(jié)點(diǎn)到各個(gè)節(jié)點(diǎn)的距離了。

圖的存儲(chǔ)：鄰接表

用 h 數(shù)組保存各個(gè)節(jié)點(diǎn)能到的第一個(gè)節(jié)點(diǎn)的編號(hào)。開始時(shí)，h[i] 全部為 -1。

用 e 數(shù)組保存節(jié)點(diǎn)編號(hào)，ne 數(shù)組保存 e 數(shù)組對(duì)應(yīng)位置的下一個(gè)節(jié)點(diǎn)所在的索引。

用 idx 保存下一個(gè) e 數(shù)組中，可以放入節(jié)點(diǎn)位置的索引

插入邊使用的頭插法，例如插入：a->b。首先把b節(jié)點(diǎn)存入e數(shù)組，e[idx] = b。然后 b 節(jié)點(diǎn)的后繼是h[a]，ne[idx] = h[a]。最后，a 的后繼更新為 b 節(jié)點(diǎn)的編號(hào)，h[a] = idx，索引指向下一個(gè)可以存儲(chǔ)節(jié)點(diǎn)的位置，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]; //鄰接表存儲(chǔ)樹，有n個(gè)節(jié)點(diǎn)，所以需要n個(gè)隊(duì)列頭節(jié)點(diǎn)static boolean[] st = new boolean[N]; //記錄節(jié)點(diǎn)是否被訪問過，訪問過則標(biāo)記為truestatic int[] d = new int[N]; //存儲(chǔ)距離static int[] e = new int[N]; //存儲(chǔ)元素static int[] ne = new int[N]; //存儲(chǔ)列表的next值static int n,m, idx; //題目所給的輸入，n個(gè)節(jié)點(diǎ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++;}}