有一棵
个点的无权无根树，求有多少个点在树的直径上。
注意：树的直径可能不止一条。
[编程题]经过直径的点
dfs思路：
1、当前点为s，记录下所有s的子结点对应的 {最大深度，所有该深度的路径上的点的总数}，把所有这样的值存到一个vector中。
比如上面这个图中，
s = 2的结点对应的应该是 { {1, 1}, {1, 1} }
s = 1的结点对应的是{ {2, 3}, {1, 1} }
2、ans = {最长的直径，该长度直径上的点的个数}，有了这样的值之后，我们考虑如何更新答案ans：
假设当前结点 s 就是直径上的一个点，
首先忽略它的父结点也在直径上的情况，因为这种情况我们在考虑父结点的时候一定会考虑到。
3、对于我们拥有的vector（记成d）因为要构成直径，必然选取两个拥有深度最大的子结点来构成直径。
也就是把我们的d按第一维降序排序，选取前两个值出来构成直径。
这里需要注意，构成的直径可能不止一个，有两种情况：
（1）d[0].first == d[1].frist，即最大的两个结点深度一样，此时可以选择任意拥有与他们相同深度的结点中的两个来组成直径，因此直径上的点的个数为
（2）d[0].first != d[1].first，此时可以选所有与第二个深度相同的点，和最大深度的点构成直径。因此
设前两个值分别是dmx, dse。
则当dmx + dse + 1 > ans.first（左边的点+右边的点+自己 构成直径 > ans的直径）时，更新ans = {dmx + dse + 1, num + 1)
4、更新完直径需要return给自己的父结点自己带有的信息:
{最大的点的深度，所有在最大深度的路径上的点的个数}，即
(对，就跟上面的第一种情况一样，加一是带上自己这个点）
5、代码：
const int MaxN = 1e5 + 5;
typedef pair<int, int> pii;
class Solution {
private:
vector<vector<int>> E;
pii ans;
pair<int, int> dfs(int s, int fa) {
vector<pii> d;
for (int i : E[s]) {
if (i == fa) continue;
pii tmp = dfs(i, s);
d.push_back(tmp);
}
sort(d.begin(), d.end());
reverse(d.begin(), d.end());
if (d.size() == 0) {
if (ans.first < 1) ans = {1, 1};
return {1, 1};
}
else {
int dmx = d[0].first;
int dse = d.size() > 1 ? d[1].first : 0;
int num = d[0].second + (d.size() > 1 ? d[1].second : 0);
for (int i = 2; i < (int)d.size(); i++) {
if (d[i].first != dse) {
break;
}
num += d[i].second;
}
if (dmx + dse + 1 > ans.first) {
ans = {dmx + dse + 1, num + 1};
}
return {dmx + 1, dmx == dse ? num + 1 : d[0].second + 1};
}
}
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 节点个数
* @param u int整型vector
* @param v int整型vector
* @return int整型
*/
int PointsOnDiameter(int n, vector<int>& u, vector<int>& v) {
E = vector<vector<int>>(n + 1);
ans = {0, 0};
for (int i = 0; i < n - 1; i++) {
E[u[i]].push_back(v[i]);
E[v[i]].push_back(u[i]);
}
dfs(1, 0);
return ans.second;
}
};
/*
附赠俩样例：
7
1 2
1 5
5 6
2 3
2 4
4 7
ans = 6
11
1 2
1 5
5 6
2 3
2 4
4 7
1 8
8 9
9 10
9 11
ans = 8
*/
发表于 2021-03-19 14:24:57
回复(0)
方法就是将给出的数据转换成一个无向连通图，然后以任意一点为起点找到距离该起点最远的点x，则x为树的直径的一个端点。使用java：
接下来：
1、再次使用BFS搜索出树的直径，然后将所有直径里的点放入一个hashSet, hashSet的大小即为直径上的点。本地测试运行正确，牛客网上运行显示在规定时间内未结束。
2，同理，使用DFS搜索出来树的直径，检测出来直径上的所有点，即为最终答案，本地测试成功，牛客网上运行显示栈溢出，原因是递归函数调用过多（一个线程分配0.5M，最后递归超过1024次）。
最后没有跑出来，可能是因为有一组测试用例数据太多，导致树过于复杂。
方法1代码：用例通过率81.82%
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 节点个数
* @param u int整型一维数组
* @param v int整型一维数组
* @return int整型
*/
private int num=0;
private int max=0;
private HashSet<Integer> hash = new HashSet<>();
// private ArrayList<boolean[]> tmp_max = new ArrayList<>();
// private ArrayList<Integer> tmp_flag = new ArrayList<>();
public int PointsOnDiameter (int n, int[] u, int[] v) {
// write code here
ArrayList<Integer>[] graph = get_graph(n, u, v);
ArrayList<Integer> end = bfs(n, graph);
D_path(n, end, graph);
return hash.size();
}
@SuppressWarnings("unchecked")
public ArrayList<Integer>[] get_graph(int n, int[] u, int[] v)
{
ArrayList<Integer>[] graph = new ArrayList[n];
for(int i=0; i<n; i++)
graph[i] = new ArrayList<>();
for(int i=0; i<u.length; i++){
graph[u[i]-1].add(v[i]-1);
graph[v[i]-1].add(u[i]-1);
}
return graph;
}
public ArrayList<Integer> bfs(int n, ArrayList<Integer>[] graph)
{
ArrayList<Integer> tmp = new ArrayList<>();
ArrayList<Integer> end = new ArrayList<>();
int[] flag = new int[n];
flag[0]=1;
tmp.add(0);
while(!tmp.isEmpty()){
end=new ArrayList<Integer>(tmp);
int len=tmp.size();
for(int j=0; j<len; j++){
int node = tmp.get(0);
for(int i=0; i<graph[node].size(); i++)
{
if(flag[graph[node].get(i)]==0)
{
flag[graph[node].get(i)]=1;
tmp.add(graph[node].get(i));
}
}
tmp.remove(0);
}
}
return end;
}
public void D_path(int n, ArrayList<Integer> end, ArrayList<Integer>[] graph){
// ArrayList<Integer> node = new ArrayList<>();
ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
ArrayList<ArrayList<Integer>> one_end_path = new ArrayList<>();
ArrayList<ArrayList<Integer>> tmp = new ArrayList<>();
for(int s=0; s<end.size(); s++){
boolean[] flag = new boolean[n];
// node.add(end.get(s));
int node = end.get(s);
ArrayList<Integer> path = new ArrayList<>();
path.add(node);
tmp.add(new ArrayList<Integer>(path));
flag[node]=true;
while(!tmp.isEmpty()){
one_end_path = new ArrayList<ArrayList<Integer>>(tmp);
int len=tmp.size();
for(int i=0; i<len; i++){
path = tmp.get(0);
int pth_node = path.get(path.size()-1);
for(int j=0; j<graph[pth_node].size(); j++){
if(flag[graph[pth_node].get(j)]==false){
flag[graph[pth_node].get(j)]=true;
path.add(graph[pth_node].get(j));
tmp.add(new ArrayList<Integer>(path));
path.remove(path.size()-1);
}
}
tmp.remove(0);
}
}
for(int i=0; i<one_end_path.size(); i++){
paths.add(one_end_path.get(i));
}
}
for(int i=0; i<paths.size(); i++){
ArrayList<Integer> path = paths.get(i);
for(int j=0; j<path.size();j++){
hash.add(path.get(j));
}
}
return;
}
} 方法2代码：用例通过率81.82% import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 节点个数
* @param u int整型一维数组
* @param v int整型一维数组
* @return int整型
*/
private int num=0;
private int max=0;
// private HashSet<Integer> hash = new HashSet<>();
private ArrayList<boolean[]> tmp_max = new ArrayList<>();
private ArrayList<Integer> tmp_flag = new ArrayList<>();
public int PointsOnDiameter (int n, int[] u, int[] v) {
// write code here
ArrayList<Integer>[] graph = get_graph(n, u, v);
ArrayList<Integer> end = bfs(n, graph);
boolean[] flag = new boolean[n];
// int[] d_node = new int[n];
for(int i=0; i<end.size(); i++){
dfs(end.get(i), graph, flag);
}
// HashSet<Integer> hash = new HashSet<>();
if(tmp_flag.size()==1){
return tmp_flag.get(0);
}
boolean res = false;
int sum = 0;
for(int i=0; i<n; i++){
res=false;
for(int j=0; j<tmp_max.size(); j++){
res = tmp_max.get(j)[i]||res;
}
if(res) sum++;
}
return sum;
}
@SuppressWarnings("unchecked")
public ArrayList<Integer>[] get_graph(int n, int[] u, int[] v)
{
ArrayList<Integer>[] graph = new ArrayList[n];
for(int i=0; i<n; i++)
graph[i] = new ArrayList<>();
for(int i=0; i<u.length; i++){
graph[u[i]-1].add(v[i]-1);
graph[v[i]-1].add(u[i]-1);
}
return graph;
}
public ArrayList<Integer> bfs(int n, ArrayList<Integer>[] graph)
{
ArrayList<Integer> tmp = new ArrayList<>();
ArrayList<Integer> end = new ArrayList<>();
int[] flag = new int[n];
flag[0]=1;
tmp.add(0);
while(!tmp.isEmpty()){
end=new ArrayList<Integer>(tmp);
int len=tmp.size();
for(int j=0; j<len; j++){
int node = tmp.get(0);
for(int i=0; i<graph[node].size(); i++)
{
if(flag[graph[node].get(i)]==0)
{
flag[graph[node].get(i)]=1;
tmp.add(graph[node].get(i));
}
}
tmp.remove(0);
}
}
return end;
}
public void dfs(int node, ArrayList<Integer>[] graph, boolean[] flag){
flag[node]=true;
num=num+1;
if(num>=max){
max=num;
int len=tmp_flag.size();
for(int i=0; i<len; i++){
if(tmp_flag.get(0)<max)
{
tmp_max.remove(0);
tmp_flag.remove(0);
}
}
tmp_max.add(flag.clone());
tmp_flag.add(max);
}
for(int i=0; i<graph[node].size(); i++){
if(flag[graph[node].get(i)]==false){
dfs(graph[node].get(i), graph, flag);
}
}
num=num-1;
flag[node]=false;
return;
}
}
编辑于 2021-03-18 22:56:06
回复(0)
问题信息
难度：
2条回答
1收藏
1300浏览
通过挑战的用户
查看代码-
2021-11-21 22:54:20
-
2021-10-07 22:24:46
-
2021-09-15 07:36:55
-
2021-08-16 13:36:50
-
2021-08-16 11:48:25
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
