846. 樹的重心-有解無憂

給定一顆樹，樹中包含n個結點（編號1~n）和n-1條無向邊，

請你找到樹的重心，并輸出將重心洗掉后，剩余各個連通塊中點數的最大值，

重心定義：重心是指樹中的一個結點，如果將這個點洗掉后，剩余各個連通塊中點數的最大值最小，那么這個節點被稱為樹的重心，

輸入格式

第一行包含整數n，表示樹的結點數，

接下來n-1行，每行包含兩個整數a和b，表示點a和點b之間存在一條邊，

輸出格式

輸出一個整數m，表示重心的所有的子樹中最大的子樹的結點數目，

資料范圍

$1 \leq n \leq 10^{5}$

輸入樣例

輸出樣例：

4

首先資料范圍10^5，用鄰接表存盤


代碼：

import java.util.Arrays;
import java.util.Scanner;

public class Main{
        static final int N=100005;
        static int h[]=new int[N];
        static int e[]=new int[N*2];//因為是無向邊，idx<=2*N，所以開兩倍空間
        static int ne[]=new int[N*2];
        static boolean vis[]=new boolean[N];
        static int n,idx,ans=N;
        static void add(int a,int b){
                e[idx]=b;
                ne[idx]=h[a];
                h[a]=idx++;
        }
        static int dfs(int u){
                vis[u]=true;
                int sum=1,res=0;
                for(int i=h[u];i!=-1;i=ne[i]){
                        int j=e[i];
                        if(!vis[j]){
                                int s=dfs(j);
                                res=Math.max(res, s);
                                sum+=s;
                        }
                }
                res=Math.max(res, n-sum);
                ans=Math.min(res, ans);
                return sum;
        }
        public static void main(String[] args) {
                Scanner scan=new Scanner(System.in);
                n=scan.nextInt();
                Arrays.fill(h,-1);//初始每個鄰接表都是空
                for(int i=0;i<n-1;i++){
                        int a=scan.nextInt();
                        int b=scan.nextInt();
                        add(a,b);
                        add(b,a);//無向圖
                }
                dfs(1);
                System.out.println(ans);
        }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/96529.html

標籤：其他

上一篇：Android螢屏適配方式問題，一般是怎么解決的，求指教！

下一篇：ListView的基礎優化方式都有哪些？