欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

搜索与图论 - 树的重心

程序员文章站 2023-12-27 08:46:45
...

1、题目描述

给定一颗树,树中包含n个结点(编号1~n)和n-1条无向边。

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤1051≤n≤105

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例:

4

2、分析

树可以看作是无环、连通的图。 

搜索与图论 - 树的重心

搜索与图论 - 树的重心 3、代码

import java.util.*;
import java.io.*;

public class Main{
    static int N = 100010;
    static int M = 2 * N;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int idx;
    static int answer = Integer.MAX_VALUE;
    static boolean[] visit = new boolean[N];
    static int n;
    
    //存储图 一条边:a -> b
    static void store(int a,int b) {
        e[idx] = b;
        ne[idx] = h[a]; //idx表示当前使用到的结点的下标
        h[a] = idx;
        idx ++;
    }
    
    //求把结点u删除后,u的每条子树分支包含的结点数量和
    static int dfs(int u) {
        visit[u] = true;
        
        int res = 0, sum = 1; //sum初始化包含当前被删除的1个结点
        
        for(int i = h[u];i != -1;i = ne[i]) {
            int val = e[i];
            if(!visit[val]) {
                int size = dfs(val);
                res = Math.max(res, size);
                sum += size;
            }
        }
        
        res = Math.max(res, n - sum); // 保存将这个点删除后,剩余各个连通块中点数的最大值
        
        answer = Math.min(answer, res);
        return sum;
    }
    
    public static void main(String[] args){
        Scanner in = new Scanner(new InputStreamReader(System.in));
        n = in.nextInt();
        
        //初始化
        for(int i = 0;i < h.length;i ++) {
            h[i] = -1;
        }
        
        for(int i = 0;i < n-1;i ++) {
            int a = in.nextInt();
            int b = in.nextInt();
            store(a, b);
            store(b, a);
        }
        
        dfs(1); //从第一个结点开始删
        
        System.out.println(answer); 
    }
    
}

 

上一篇:

下一篇: