C++ 代码

//没有环的连接图为树
//利用除根节点之外的其它结点只能同时容纳一个人的性质
//则最短疏散时间=根结点中节点数最多的子树的节点数
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1e5+10,M=N*2;
int n;
int h[N],e[M],ne[M],idx;

int q[N];
bool st[N];


void add(int a,int b)//数组模拟邻接表的插入方式
{
    e[idx]=b;//创立新的结点
    ne[idx]=h[a];//next指针指向h[a]
    h[a]=idx;
    idx++;

}

//递归层数过多时，栈内存不够用，改为bfs
int dfs(int u,int father)
{
    int res=1;
    for(int i=h[u];i!=-1;i=ne[i])//遍历u的初边
    {
        int son=e[i];
        if(son!=father) res+=dfs(son,u);
    }
    return res;
}

int bfs(int u)//宽搜需要自己写栈操作
{
    int hh=0,tt=0;
    q[0]=u;
    st[u]=true;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int son=e[i];
            if(!st[son])
            {
                q[++tt]=son;
                st[son]=true;
            }

        }
    }
    return tt+1;  //尾加1
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof(h));//h全部赋为空
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);//无向
    }
    int res=0;
    for(int i=h[1];i!=-1;i=ne[i])
    {
        res=max(res,dfs(e[i],1));
    }
    cout<<res<<endl;
    return 0;
}