PAT1021 Deepest Root（求树的最大深度）

分析：题目给了你n个点和n-1条边。
要求：（1）判该图断是不是联通，不连通输出联通块数目。dfs即可
（2）联通，给出从那个点开始遍历可以得到树的最大深度，要有多个点依次输出。bfs
感觉自己虽然过了这道题，但是写的很丑。。

#include<bits/stdc++.h>
using namespace std;
int n,cnt,vis[11000],ans,ha[11000],res,visit[11000];
int maxLevel[11000];
bool flag=true;
vector<int> ve[11000];
void bfs(int s){
    memset(maxLevel,0,sizeof(maxLevel));memset(vis,0,sizeof(vis));cnt=0;ans=0;queue<int> que;que.push(s);maxLevel[s]=1;cnt++;vis[s]=1;while(!que.empty()){
    int q1,q2,q3;q1=que.front();que.pop();//cout<<q1<<endl;for(int i=0;i<ve[q1].size();i++){
    if(!vis[ve[q1][i]]){
    que.push(ve[q1][i]);vis[ve[q1][i]]=1;cnt++;maxLevel[ve[q1][i]]=maxLevel[q1]+1;}}}if(cnt<n){
    flag=false;}else {
    for(int i=1;i<=n;i++){
    ans=max(ans,maxLevel[i]);}}
}
void dfs(int x){
    visit[x]=1;for(int i=0;i<ve[x].size();i++){
    if(!visit[ve[x][i]]){
    dfs(ve[x][i]);}}
}
int main(){
    std::ios::sync_with_stdio(false);cin>>n;int m=n-1;for(int i=0;i<m;i++){
    int x,y;cin>>x>>y;ve[x].push_back(y);ve[y].push_back(x);}for(int i=1;i<=n;i++){
    bfs(i);ha[i]=ans;res=max(res,ans);}//cout<<flag<<endl;if(flag){
    for(int i=1;i<=n;i++){
    if(ha[i]==res){
    cout<<i<<endl;}}}else{
    int tmp=0;for(int i=1;i<=n;i++){
    if(!visit[i]){
    dfs(i);tmp++;}}cout<<"Error: "<<tmp<<" components"<<endl;}return 0;
}