题目描述

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤105

输入样例

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

输出样例

4

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=100010,M=N*2;     //n的数据范围是 10的五次方，因为是无向图，一组数据里就有两个元素，两个next指针 ，所以M=2*N 
int n;                        //n是结点的个数 
int h[N],e[M],ne[M],idx,ans=N;//h[]表示头结点，e[],ne[],idx均和单链表的意思相同,e[]存储当前结点的元素,ne[]存储当前结点指向下一个节点的next指针,idx表示当前结点已经使用的位置，详情请看yxc的单链表讲解视频（网址附在下方）
bool stl[N];                  //来表示当前这个结点是否有被用到

void add(int a,int b)         //通过邻接表，将b插到a下
{
    e[idx]=b;
    ne[idx]=h[a];             //从头插入，具体详情请看详情请看yxc的单链表讲解视频（网址附在下方）
    h[a]=idx;
    idx++;
}

int dfs(int u)                //返回包括u点在内的，以u为根的子树结点的个数
{
    int res=0,sum=1;          //res存储当前连通块中结点的最大数目，sum存储包括u点在内的，以u为根的子树结点的个数
    stl[u]=true;              //因为已经走到u这个点了，所以u=true

    for(int i=h[u];i!=-1;i=ne[i])   //从链表头开始循环，到链表尾结束，具体详情请看详情请看yxc的单链表讲解视频（网址附在下方）
    {
        int j=e[i];                 //用e[i]中存储的数字当做编号，来看看这个数字有没有被查询过
        if(stl[j]==false)
        {
            int s=dfs(j);           //s是以包括j点在内的，以j为根的子树结点的个数（递归）
            res=max(res,s);         //通过max比对出最大的连通块结点数目
            sum=sum+s;              //sun加上以j为根的子树结点的个数
        }
    }
    res=max(res,n-sum);             //最后在比对一下包括j点在内的，以j为根的子树结点的个数和不是以j为根的子树的结点个数，哪个较大
    ans=min(res,ans);               //最后在所有最大的连通块结点数目找到最小值
    return sum;                     //返回包括u点在内的，以u为根的子树结点的个数，因为每一层递归都要将sum不断增加
}

int main()
{
    memset(h,-1,sizeof h);          //先将h[]数组初始化成-1，是链表为空
    scanf("%d",&n);                 //输入结点数n
    for(int i=0;i<n-1;i++)          //每两个点之间有一条线，所以n个点只要输入n-1组数据（线），又因为从0开始循环，所以一直循环到<n-1
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);          //因为是无向图，所以既可以a→b，也可以b→a
    }
    dfs(1);                         //dfs可以从任意一个点开始寻找，u<=n

    printf("%d",ans);               //输出所有最大的连通块结点数目中的最小值

    return 0;
}

附：yxc单链表讲解视频

yxc单链表讲解视频

心得

这道题目结合了很多前面的知识（算法基础课），很抽象，它结合了单链表（邻接表），和树的知识