[数据结构与算法]1581 旅游规划(LOJ10159) 找树的直径上所有点 两次深搜20分 三次深搜100分

总目录

在线测评地址(ybt)

在线测评地址(LOJ)

样例图形对应如下：

基本思路：先以0为根节点，标记出所有节点的深度，在以其中最大深度的节点为根节点，重新标记所有节点的深度，深度最大的节点都在链的最远端。

如何标记链上的点，想了想，可以由深度最大的点开始，找父节点，直到找到根节点。

ybt

未通过

LOJ

?20分代码如下：

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int head[maxn],tot,n,mx,k;
int dep[maxn],fa[maxn],vis[maxn];
struct node{
	int to,next;
}e[maxn<<1];
void add(int u,int v){
	tot++,e[tot].to=v,e[tot].next=head[u],head[u]=tot;
}
void dfs(int u,int f){
	int i,v;
	for(i=head[u];i;i=e[i].next){
		v=e[i].to;
		if(v==f){
			fa[u]=f;
			continue;
		}
		dep[v]=dep[u]+1;
		if(mx<=dep[v])mx=dep[v],k=v;//请注意此处不是mx<dep[v] 
		dfs(v,u);
	}
}
void init(){
	int i,u,v;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
}
void find(int x){
	if(vis[x])return;
	vis[x]=1;
	find(fa[x]);
}
int main(){
	int u;
	init();
	dep[0]=0;
	dfs(0,-1);
	dep[k]=0;
	vis[k]=1;//请注意，此处vis[k]放的位置 
	dfs(k,-1);
	for(u=0;u<n;u++)
		if(dep[u]==mx)
			find(u);
	for(u=0;u<n;u++)
		if(vis[u])
			printf("%d\n",u);
	return 0;
}

想不通，为何会错，直到看到了这副图：

对应的输入输出数据如下：

输入:
7
0 1
1 2
2 3
3 4
2 5
5 6

输出：
0
1
2
3
4
5
6

上述代码对应的输出数据如下：

0
1
2
3

显然是错的，明白了错误，再看看能否将代码修改。

很显然，树的直径是找到了，但是没找全。

显然，找数的直径过程中，将两个端点分别作为根，进行查找，这样，就能找全，添加代码，上述例子通过，提交AC.

ybt

通过

LOJ

三次深搜找树的直径上所有点

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int head[maxn],tot,n,mx,k;
int dep[maxn],fa[maxn],vis[maxn];
struct node{
	int to,next;
}e[maxn<<1];
void add(int u,int v){
	tot++,e[tot].to=v,e[tot].next=head[u],head[u]=tot;
}
void dfs(int u,int f){
	int i,v;
	for(i=head[u];i;i=e[i].next){
		v=e[i].to;
		if(v==f){
			fa[u]=f;
			continue;
		}
		dep[v]=dep[u]+1;
		if(mx<=dep[v])mx=dep[v],k=v;
		dfs(v,u);
	}
}
void init(){
	int i,u,v;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
}
void find(int x){
	if(vis[x])return;
	vis[x]=1;
	find(fa[x]);
}
int main(){
	int u;
	init();
	dep[0]=0;
	dfs(0,-1);//第一次深搜 
	dep[k]=0;
	vis[k]=1; 
	dfs(k,-1);//第二次深搜,找出树的直径 
	for(u=0;u<n;u++)
		if(dep[u]==mx)
			k=u,find(u);
	dfs(k,-1);//第三次深搜,换个端点,找出树的直径
	for(u=0;u<n;u++)
		if(dep[u]==mx)
			find(u); 
	for(u=0;u<n;u++)
		if(vis[u])
			printf("%d\n",u);
	return 0;
}

?通过树的深度找树的直径是一种办法，还想看看他人是怎么找树的直径的。

该题习得什么？

要找全所有树的直径上的点，要三次深搜。

?