846. 树的重心

佚名 4年前 (2020-02-03) 算法 1326人围观抢沙发百度已收录

给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数n，表示树的结点数。

接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。

输出格式

输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。

数据范围

1≤n≤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);
        }
}