AcWing846. 树的重心（C++算法）

AcWing846. 树的重心

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

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

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

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

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

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

数据范围
1≤n≤10⁵

输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4

2、基本思想：
用深度搜索，假设有n个节点。记录每一个节点，以u为例，先以u为根节点，遍历它的每个子树（假设子树编号为1、2、3）期间记录u树的节点个数和sum（包括根），记录含有节点个数最多的那个子树（假设是1号子树），最后比较这个1号子树和（n - sum）的大小，选出最小值。以此类推遍历整个树中其他节点。

3、C ++ 代码如下（该代码引用AcWing网站代码）

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

using namespace std;

const int N = 100010;

int n;
int h[N], e[N * 2], ne[N * 2], idx;//因为是无向边所以每条边会存两次，所以N*2.
int ans = N;//最终输出答案
bool st[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 size = 1, sum = 1;//原本的根节点算一个所以开始为1
    for (int i = h[u]; i != - 1; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;
        
        int s = dfs(j);
        sum += s;
        size = max(size, s);//记录最大联通子图的节点数
    }
    size = max(size, n - sum);//比较以u为根最大联通子图节点数与去掉以u为根的所有节点，看谁最大
    ans = min(ans, size);
    
    return sum;
}


int main()
{
    cin >> n;
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);//是无向边要存两次。
    }
    
    dfs(1);//从1~n任意一个数开始都可以。
    
    cout << ans;
    
    return 0;
}