題目

一棵樹的直徑就是這棵樹上存在的最長路徑?，F(xiàn)在有一棵n個節(jié)點的樹，現(xiàn)在想知道這棵樹的直徑包含的邊的個數(shù)是多少？

如圖所示的數(shù)據(jù)，這棵樹的直徑為(1-2-3-6-9)這條路徑，包含的邊的個數(shù)為4，所以答案是4。

輸入

第1行：一個整數(shù)n，表示樹上的節(jié)點個數(shù)。(1<=n<=100000)
第2-n行：每行有兩個整數(shù)u,v,表示u與v之間有一條路徑。(1<=u,v<=n)

輸出

輸出一個整數(shù)，表示這棵樹直徑所包含的邊的個數(shù)。

輸入樣例

10
1 2
2 3
3 4
3 5
3 6
3 7
3 10
6 8
6 9

輸出樣例

4

思路：樹的直徑模版題，由于輸入無邊權(quán)，因此將邊權(quán)賦為 1 即可

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 500000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;struct Edge{int w;int from,to;int next; }edge[N]; int head[N],edgeNum=0; int n,m; int dis[N*2]; bool vis[N]; int start,endd; void addEdge(int from,int to,int w) {edge[++edgeNum].to=to;edge[edgeNum].w=w;edge[edgeNum].next=head[from];edge[edgeNum].from=from;head[from]=edgeNum; } void dfs(int x) {vis[x]=true;for(int i=head[x];i!=-1;i=edge[i].next){int to=edge[i].to;if(!vis[to]) {dis[to]=dis[x]+edge[i].w;dfs(to);}} } int main() {scanf("%d",&n);memset(head,-1,sizeof(head));edgeNum=0;m=n-1;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addEdge(x,y,1);addEdge(y,x,1);}memset(vis,false,sizeof(vis));memset(dis,INF,sizeof(dis));dis[1]=0;dfs(1);//從1號點開始找最遠(yuǎn)的點int maxx=-INF;for(int i=1;i<=n;i++){if(dis[i]>maxx&&dis[i]!=INF) {maxx=dis[i];start=i;//樹的直徑的起點}}memset(vis,false,sizeof(vis));memset(dis,INF,sizeof(dis));dis[start]=0;dfs(start);maxx=-INF;for(int i=1;i<=n;i++){if(dis[i]>maxx&&dis[i]!=INF) {maxx=dis[i];endd=i;//樹的直徑的終點}}printf("%d\n",maxx);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的树的直径（51Nod-2602）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。