欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1021 Deepest Root (测试点4、5报错的解决办法)

程序员文章站 2024-03-21 23:35:58
...

(代码来自柳婼https://github.com/liuchuo/PAT/blob/master/AdvancedLevel_C%2B%2B/1021.%20Deepest%20Root%20(25)%20.cpp)

步骤:
①先以节点1为根节点进行DFS,找出最长的几个路径的终点temp[ ]并输入到set中,同时记录连通分量个数cnt
(这里必须把终点全部输入到set中,如果只输入temp[0],测试点4、5会出错,因为题目给的树可能是分叉的)
例:如下图 ,只存temp[0]会使得结果为 1 5,而正确结果应该是 1 4 5

1021 Deepest Root (测试点4、5报错的解决办法)

②若cnt > 1,则非树,输出 Error: K components
若cnt==1,则为树,继续进行

#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
using namespace std;

int n,cnt=0,s1,h=0,maxh=0,visit[10010]={};
set<int> st;
set<int>::iterator it;
vector<int> temp;
vector<vector<int> > q;
void dfs(int node,int h){
    if(h>maxh){
        maxh=h;
        temp.clear();
        temp.push_back(node);
    }
    else if(h==maxh)
            temp.push_back(node);

    visit[node]=1;
    for(int i=0;i<q[node].size();i++){
        if(visit[q[node][i]]==0){
            dfs(q[node][i],h+1);
        }
    }
}
int main()
{
    cin>>n;
    q.resize(n+2);
    int a,b;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        q[a].push_back(b);
        q[b].push_back(a);
    }

    for(int i=1;i<=n;i++){
        if(visit[i]==0){
            dfs(i,1);
            if(!temp.empty()) s1=temp[0];
            for(int i=0;i<temp.size();i++)   //这里要把temp中的全部存入set中,因为可能有分叉的
                st.insert(temp[i]);
            cnt++;
        }
    }
    if(cnt>1){
        cout<<"Error: "<<cnt<<" components";
        return 0;
    }
    else{
        h=0,maxh=0;
        temp.clear();
        for(int i=0;i<10010;i++) visit[i]=0;
        dfs(s1,1);
        for(int i=0;i<temp.size();i++)
            st.insert(temp[i]);
        for(it=st.begin();it!=st.end();it++)
            cout<<*it<<endl;
    }
    return 0;
}