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
②若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;
}
上一篇: Python课程第八周笔记及作业