1021 Deepest Root (25 分) 【难度: 中 / 知识点: 树的直径 连通块】

https://pintia.cn/problem-sets/994805342720868352/problems/994805482919673856
方法一:

• 数组模拟邻接表
• 第一步: 爆搜dfs求连通块
• 第二步: 暴力枚举每一个点求其最远的距离

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int h[N],e[N],ne[N],idx,n; int st[N],cnt; void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u)//求连通块 {st[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i]; if(!st[j]) dfs(j);} } int dfs1(int u,int father)// u当前的点 father从哪里来的 {int depth=0;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==father) continue;//走回头路了depth=max(depth,dfs1(j,u)+1); }return depth;//该点的最大深度 } int main(void) {cin>>n;memset(h,-1,sizeof h);for(int i=0;i<n-1;i++){int a,b; cin>>a>>b;add(a,b),add(b,a);}for(int i=1;i<=n;i++) if(!st[i]) dfs(i),cnt++;//求联通块的个数if(cnt==1){vector<int>ve;int max_len=0;//最深的深度for(int i=1;i<=n;i++){int len=dfs1(i,-1);if(len>max_len)//有更深的{max_len=len;ve.clear();ve.push_back(i);}else if(len==max_len) ve.push_back(i);//并列}for(int i=0;i<ve.size();i++) cout<<ve[i]<<endl;}else printf("Error: %d components",cnt);return 0; }

方法二:

• vector存邻接表
• 第一步: 并查集求连通块
• 第二步: 暴力枚举每一个点求其最远的距离

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; vector<int>ve[N]; int p[N],n; int find(int x) {if(x!=p[x]) p[x]=find(p[x]);return p[x]; } int dfs(int u,int father) {int depth=0;for(int i=0;i<ve[u].size();i++){if(ve[u][i]==father) continue;depth=max(depth,dfs(ve[u][i],u)+1);}return depth; } int main(void) {cin>>n; int cnt=n;//初始每一个点都是一个连通块。for(int i=1;i<=n;i++) p[i]=i;for(int i=0;i<n-1;i++){int a,b; scanf("%d%d",&a,&b);ve[a].push_back(b);ve[b].push_back(a);if(find(a)!=find(b))//合并{p[find(a)]=find(b);cnt--;//合并之后连通块的数量减一}}if(cnt>1) printf("Error: %d components",cnt);else {vector<int>ans;int max_len=0;for(int i=1;i<=n;i++){int len=dfs(i,-1);if(len>max_len){max_len=len;ans.clear();ans.push_back(i);}else if(len==max_len) ans.push_back(i);}for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]);}return 0; }

时间上的比较: 第一种比第二种快了[100,300]ms 如果第一种也用并查集时间会更快。第二种的vector的时间花费有点大

总结

以上是生活随笔为你收集整理的1021 Deepest Root (25 分) 【难度: 中 / 知识点: 树的直径 连通块】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。