本文主要是介绍SDUT OJ 3045 迷之图论 (树的直径)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：SDUT OJ 3045
这题比赛的时候想的差不多。。但是总是觉得不对。。写了一次就没再写，然后删了。。当时没想到的是第二次求出来的就是最长链。。当时想到的两次bfs找最大值（这一种方法其实结果也对。。TAT。。），还有找到点后在回溯减去重点等等。。但总觉得好像都不太对。。。赛后才知道这题原来是树的直径。。。。。牡丹江区域现场赛的时候遇到过，不过赛后也没看。。。
找树的直径的方法其实就是先任取一点进行bfs，找到最远的一点，这时最远的一点肯定是最长链端点之一，然后再从这一最远点开始bfs，这时另一个端点就找到了，长度就是bfs的深度。
看的其他地方的证明如下：
关键在于证明第一次遍历的正确性，也就是对于任意点u，距离它最远的点v一定是最长路的一端。
如果u在最长路上，那么v一定是最长路的一端。可以用反证法：假设v不是最长路的一端，则存在另一点v’使得(u→v’)是最长路的一部分，于是len(u→v’) > len(u→v)。但这与条件“v是距u最远的点”矛盾。
如果u不在最长路上，则u到其距最远点v的路与最长路一定有一交点c，且(c→v)与最长路的后半段重合(why?)，即v一定是最长路的一端。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
int head[110001], cnt, vis[110001], pos, d;
struct node {int u, v, next;
} edge[210001];
void add(int u, int v)
{edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;
}
struct node1 {int n, ans;
};
void bfs(int source)
{memset(vis,0,sizeof(vis));vis[source]=1;node1 f1, f2;queue<node1>q;f1.n=source;f1.ans=0;q.push(f1);while(!q.empty()) {f1=q.front();pos=f1.n;d=f1.ans;q.pop();int u=f1.n;for(int i=head[u]; i!=-1; i=edge[i].next) {int v=edge[i].v;if(!vis[v]) {f2.n=v;f2.ans=f1.ans+1;vis[v]=1;q.push(f2);}}}
}
int main()
{int n, i, j, u, v;while(scanf("%d",&n)!=EOF) {if(n==1) {printf("1\n");continue ;}memset(head,-1,sizeof(head));cnt=0;for(i=0; i<n-1; i++) {scanf("%d%d",&u,&v);add(u,v);add(v,u);}bfs(1);bfs(pos);printf("%d\n",d+1);}return 0;
}
这篇关于SDUT OJ 3045 迷之图论 (树的直径)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
