PAT甲1021 Deepest Root (25)（25 分）

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;

vector<int> G[10010];
int height[10010];
bool vis[10010];
int N;

int BFS(int now,int &total)
{
    queue<int> q;
    q.push(now);
    int last=now,preend=now;
    int height=0;
    vis[now]=true;
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        total++;
        for(int i=0;i<G[top].size();i++)
        {
            if(vis[G[top][i]]==false)
            {
                q.push(G[top][i]);
                vis[G[top][i]]=true;
                last=G[top][i];
            }
        }
        if(top==preend)
        {
            height++;
            preend=last;
        }
    }
    return height;
}

int BFST(int now,int &h)
{
    int num=1;
    int total=0;
    h=BFS(now,total);
    if(total<N)
    {
        for(int i=1;i<=N;i++)
        {
            if(vis[i]==false)
            {
                BFS(i,total);
                num++;
            }
        }
    }
    return num;
}

int main()
{
    scanf("%d",&N);
    for(int i=0;i<N-1;i++)
    {
        int v1,v2;
        scanf("%d%d",&v1,&v2);
        G[v1].push_back(v2);
        G[v2].push_back(v1);
    }
    int maxh=-1;
    for(int i=1;i<=N;i++)
    {
        memset(vis,false,sizeof(vis));
        int h=0;
        int num=BFST(i,h);
        if(num>1)
        {
            printf("Error: %d components",num);
            break;
        }
        else
        {
            height[i]=h;
            maxh=max(maxh,h);
        }
    }
    for(int i=1;i<=N;i++)
    {
        if(height[i]==maxh)
        {
            printf("%d\n",i);
        }
    }
    return 0;
}