想去偷脑子 2022-08-03 16:02
浏览 4
已结题

树的重心代码里的n-size是不是没必要的

问题:给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
输入格式
第一行包含整数 n,表示树的结点数。
接下来 n−1行,每行包含两个整数 a 和 b,表示点 a 和点 b之间存在一条边。
输出格式
输出一个整数 m,表示将重心删除后,剩余各个连通块中点数的最大值。
数据范围
1≤n≤105

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];

int ans = N;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u)
{
    st[u] = true;
    
    int sum = 1, res = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }
    
    res = max(res, n - sum);
    
    ans = min(ans, res);
    
    return sum;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    dfs(1);
    
    cout << ans << endl;
    
    return 0;
}

img

我不理解n-size,我觉得它已经是被删除点的子树集了,它是被包括在for(int i = h[u])里面的了

  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 8月11日
    • 创建了问题 8月3日

    悬赏问题

    • ¥15 用conda install时失败
    • ¥15 第三方如何控制E8a进行烧录
    • ¥15 关于lua调用DLL的c/c++动态库(相关搜索:数据库)
    • ¥15 openwrt结合智能家居(相关搜索:路由器)
    • ¥15 求一款免费的pdf编辑js,web端用的
    • ¥20 UE5.2插件Remote Control Web Interface安装失败问题
    • ¥15 求分析下图晶体与三极管组成的振荡电路
    • ¥100 多线程+连接池+代理 运行一段时间线程阻塞
    • ¥15 关于#单片机#的问题:求一个使用C语言将重力加速度gx,gy,gz积分获取到速度的代码(相关搜索:c语言)
    • ¥15 matlab导致电脑重启问题