首页 > 代码库 > 树讲解（2）——树的输入，重心，直径
树讲解（2）——树的输入，重心，直径
one.树的输入
1.输入每个节点父亲节点的编号
#include<vector>#include<stdio.h>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 100000#define maxn 123456using namespace std;int n,x,fa[N];bool vis[N];vector<int>vec[N];void dfs(int x){ vis[x]=1; for(int i=0;i<vec[x].size();i++) dfs(vec[x][i]); }int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&x); fa[i]=x; vec[x].push_back(i);//由x向i连一条有向边 } dfs(1);}
2.直接输入树上n-1条边，不确定根
#include<vector>#include<stdio.h>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 10000#define maxn 123456using namespace std;vector<int>vec[N];int n,x,y,fa[N];bool vis[N];void dfs(int x){ vis[x]=1; for(int i=0;i<vec[x].size();i++) { if(vec[x][i]!=fa[x]) { fa[vec[x][i]]=x; dfs(vec[x][i]); } }}int main(){ scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); vec[x].push_back(y); vec[y].push_back(x); } dfs(1); return 0;}
two。树的直径
树的直径即为在这棵树上最长的简单路径。
做法：
首先，我们先随便找一个点为各节点对整棵树进行一下dfs，求出离这个点最远的节点t
然后，我们在以t点为根节点对整棵树进行一下dfs，求出这个点最远的节点m
这样我们就称tm是这棵树的直径！
求树的直径的代码
#include<vector>#include<stdio.h>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 10000#define maxn 123456 using namespace std;vector<int>vec[N];int n,x,y,fa[N],s,t,dis[N];void dfs(int x){ for(int i=0;i<vec[x].size();i++) { if(!dis[vec[x][i]]) { dis[vec[x][i]]=dis[x]+1; dfs(vec[x][i]); } }}int main(){ scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); vec[x].push_back(y); vec[y].push_back(x); } dis[1]=1; dfs(1); for(int i=t=1;i<=n;i++) if(dis[t]>dis[i]) t=i; memset(dis,0,sizeof(dis)); dis[t]=1; dfs(t); for(int i=s=1;i<=n;i++) if(dis[s]>dis[i]) s=i; printf("%d",dis[s]-1); return 0; }
three。树的重心
找到一个点，若这个点满足他的子树中的最大子节点数最少，那这个点就是树的重心
在树的总点数是偶数的时候，一个树可能有两个重心。
在找树的重心时，随意确定一个根，对整棵树进行一遍dfs，找出每个节点的子节点的个数
一棵树的重心满足他的子节点的个数：2*sizei>=n,但他的子节点2*sizei<=n，那这个点就是树的重心
代码
#include<vector>#include<stdio.h>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 100000#define maxn 123456using namespace std;vector<int>vec[N];int n,x,y,ans,size[N],fa[N];void dfs(int x){ size[x]=1; for(int i=0;i<vec[x].size();i++) { if(fa[x]!=vec[x][i]) { fa[vec[x][i]]=x; dfs(vec[x][i]); size[x]+=size[vec[x][i]]; } } if(!ans&&size[x]*2>=n) ans=x;}int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); vec[x].push_back(y); vec[y].push_back(x); } dfs(1); printf("%d",ans); return 0;}
就算慢又怎样，一步一个脚印，回头看时，还是有别样的风采！
树讲解（2）——树的输入，重心，直径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。