16 条回复
感谢提醒思路...
import java.util.LinkedList;
import java.util.List;
public class Main1 {
static class Node {
int data;
List<Node> list = new LinkedList<>();
public Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
int n = 4;
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
n1.list.add(n2); n1.list.add(n3);
n3.list.add(n4);
System.out.println(2 * (n - 1) - height(n1));
}
private static int height(Node root) {
LinkedList<Node> list = new LinkedList<>();
list.add(root);
int height = -1;
while (!list.isEmpty()) {
height ++;
int size = list.size();
for (int i = 0; i < size; i++) {
list.addAll(list.removeFirst().list);
}
}
return height;
}
}# -*- coding=utf-8 -*- import sys from collections import defaultdict def get_max_depth(temp_dict): """得到最大深度：此时计算的深度为边的个数， Args: temp_dict (dict): 保存有节点单向连边的字典 Returns: int: 最大深度 """ res = [] length = 0 for item in temp_dict[1]: get_depth(item, temp_dict, length, res) return max(res) def get_depth(item, temp_dict, length, res): """取得从节点1每一个子树出发的最大深度 Args: item (int): 当前节点 temp_dict (dict): 保存有连接情况的节点 length (int): 当前长度 res (list): 保存有最大深度的数组 """ length += 1 if not temp_dict[item]: res.append(length) return for item in temp_dict[item]: get_depth(item, temp_dict, length, res) if __name__ == "__main__": n = int(sys.stdin.readline().strip()) temp_dict = defaultdict(list) for i in range(n-1): n1, n2 = map(int, sys.stdin.readline().strip().split()) if n2 < n1: n1, n2 = n2, n1 temp_dict[n1].append(n2) print(2 * (n - 1) - get_max_depth(temp_dict))
相当于一棵树，找到到子节点最长的一条路径，不用走俩次，其他的都需要走俩次。
这道题先用python写的，只通过73%，换成C++就AC了。
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> v;
int fd(int father,int current)
{
int i;
int max_len=0,len;
for(i=0;i<v[current].size();i++)
{
if(v[current][i]!= father)
{
len=fd(current,v[current][i]);
if(len>max_len)max_len=len;
}
}
return max_len+1;
}
int main() {
int n;
cin >> n;
int i;
int x, y;
v.resize(n);
for (i = 0; i < n - 1; i++)
{
cin >> x >> y;
v[x - 1].push_back(y - 1);
v[y - 1].push_back(x - 1);
}
int max_len = 0, len;
for (i = 0; i < v[0].size(); i++)
{
len = fd(0, v[0][i]);
if (len > max_len)max_len = len;
}
cout<<max_len+(n-max_len-1)*2<<endl;
return 0;
}
第一题图的遍历，思路 (n-1)*2-图最大遍历深度
AC代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MAXN 100010
int g[MAXN][100];
int f[MAXN];
int isv[MAXN];
int maxn = 0;
void dfs(int curp,int curs)
{
int i;
// 当前节点走过了
isv[curp] = 1;
// 当前节点是否全部走过，默认为是
bool isallv = true;
for(i=0;i<f[curp];i++){
if( ! isv[g[curp][i]]){
// 当前节点的第 i 个子节点没有被走过，那么可以走
isallv = false;
dfs(g[curp][i],curs+1);
}
}
if(isallv){
//当前节点的所有子节点都被走过，那么不能再走了，计算走到这儿的最大深度
if(curs>maxn)
maxn = curs;
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
if(n==0) break;
memset(g,0,sizeof(g));
memset(f,0,sizeof(f));
memset(isv,0,sizeof(isv));
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
g[a][f[a]++] = b;
g[b][f[b]++] = a;
}
dfs(1,0);
printf("%d\n",(n-1)*2-maxn);
}
return 0;
}
添加回复
isaimawang
@ 赛码网
533869549