首页 > 试题广场 >

图的遍历

[编程题]图的遍历
  • 热度指数:8258 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给定一张包含 个点、 N-1 条边的无向连通图,节点从 到 编号,每条边的长度均为 。假设你从 号节点出发并打算遍历所有节点,那么总路程至少是多少?

数据范围:

输入描述:
第一行包含一个整数N。

接下来N-1行,每行包含两个整数X和Y,表示X号节点和Y号节点之间有一条边。


输出描述:
输出总路程的最小值。
示例1

输入

4
1 2
1 3
3 4

输出

4
示例2

输入

2
1 2

输出

1
#include <bits/stdc++.h>
using namespace std;

int sum = 0;
const int N = 100003;
vector<int> v[N];

void DFS(int x, int pre, int w){
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=pre)
            DFS(v[x][i], x, w+1);
    }
    sum = max(sum, w);
}

int main(){
    int n,x,y;
    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1, -1, 0);
    cout<<2*(n-1)-sum<<endl;
    return 0;
}

发表于 2019-09-28 10:05:56 回复(0)
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<List<Integer>> map = new ArrayList<>(n + 1);

        for (int i = 0; i <= n; i++) {
            map.add(new ArrayList<>());
        }

        for (int i = 1; i <= n - 1; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            List<Integer> lst = map.get(x);
            lst.add(y);
            lst = map.get(y);
            lst.add(x);
        }

        boolean[] vis = new boolean[n + 1];

        class Element {
            private int point;
            private int deep;
            private Element(int point, int deep) {
                this.point = point;
                this.deep = deep;
            }
        }

        Queue<Element> queue = new LinkedList<>();
        queue.add(new Element(1, 0));
        vis[1] = true;
        int max = 0;
        while (!queue.isEmpty()) {
            Element p = queue.poll();

            if(p.deep > max) {
                max = p.deep;
            }

            List<Integer> lst = map.get(p.point);
            if(lst.isEmpty()) {
                continue;
            }

            for (int t : lst) {
                if(!vis[t]) {
                    vis[t] = true;
                    queue.add(new Element(t, p.deep + 1));
                }
            }
        }

        System.out.println(2 * (n - 1) - max);
    }

}

发表于 2019-09-15 16:48:18 回复(1)
#include <iostream>
#include <vector>

using namespace std;

int maxDepth(vector<vector<int>>& g, vector<int>& vis, int curr) {
  vis[curr] = 1;
  int max_depth = 0;
  for (const int nxt : g[curr]) {
    if (vis[nxt]) continue;
    int depth = maxDepth(g, vis, nxt);
    max_depth = max(max_depth, depth);
  }
  return 1 + max_depth;
}

int main(const int argc, const char* argv[]) {
  int n;
  cin >> n;
  vector<vector<int>> g(n + 1);
  vector<int> vis(n + 1, 0);
  int u, v;
  for (int i = 0; i < n - 1; ++i) {
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  cout << (n << 1) - maxDepth(g, vis, 1) - 1;
  return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>

#define OK 1
#define ERROR -1
#define MEMORY_OVERFLOW -2

#define NOT !

#define DEFAULT_CAPACITY 1E5
#define InitQueue(Q) __InitQueue(Q, DEFAULT_CAPACITY)

typedef int Status;

// ==================== 循环队列存储结构表示与实现 ====================
typedef int QElemType;

typedef struct CircularQueue {
  QElemType* base;
  int front;
  int rear;
  size_t capacity;
} SqQueue;


Status __InitQueue(SqQueue* Q, int initialCapacity) {
  if (initialCapacity < 1) {
    fprintf(stderr,
            "__InitQueue ERROR: The intitialCapacity %d Must be > 0!",
            initialCapacity);
    return ERROR;
  }
  if (!((*Q).base = (QElemType*) malloc((initialCapacity + 1) * sizeof(QElemType)))) {
    fprintf(stderr, "__InitQueue Memory Overflow: %s\n", strerror(errno));
    exit(MEMORY_OVERFLOW);
  }
  (*Q).front = (*Q).rear = 0;
  (*Q).capacity = initialCapacity + 1;
  return 0;
}

bool QueueEmpty(SqQueue* Q) {
  return (*Q).front == (*Q).rear;
}

bool QueueFull(SqQueue* Q) {
  return ((*Q).rear + 1) % (*Q).capacity == (*Q).front;
}

size_t QueueLength(SqQueue* Q) {
  return ((*Q).rear - (*Q).front + (*Q).capacity) % (*Q).capacity;
}

void __large_capacity(SqQueue* Q) { 
}

Status EnQueue(SqQueue* Q, QElemType e) {
  if (QueueFull(Q))
    __large_capacity(Q);
  
  (*Q).rear = ((*Q).rear + 1) % (*Q).capacity;
  *((*Q).base + (*Q).rear) = e;
  return OK;
}

Status DeQueue(SqQueue* Q, QElemType* e) {
  if (QueueEmpty(Q)) {
    fputs("DeQueue ERROR: The queue is empty!", stderr);
    return ERROR;
  }
  (*Q).front = ((*Q).front + 1) % (*Q).capacity;
  *e = *((*Q).base + (*Q).front);
  return OK;
}

Status DestroyQueue(SqQueue* Q) {
  free((*Q).base);
  return OK;
}
// ==================== 循环队列存储结构表示与实现 ====================

// ==================== The begin of function prototype ====================
void addEdge(int* head, int* to, int* next, const int u, const int v, int* edge_count);
void printGraph(int* head, int* to, int* next, const int n);
int breath_first_search_algorithm(const int n, int* head, int* to, int* next);
// ==================== The begin of function prototype ====================


int main(const int argc, char** argv) {
  int n;
  fscanf(stdin, "%d", &n);
  
  // 图的邻接链表(adjacency list)表示法
  int m = n - 1; // m为边的数量
  int head[n + 1], to[m << 1 + 1], next[m << 1 + 1];
  memset(head, 0x0000, sizeof head);
  
  int u, v, edge_count = 0;
  while (m--) { // 构建无向图
    fscanf(stdin, "%d %d", &u, &v);
    addEdge(head, to, next, u, v, &edge_count);
    addEdge(head, to, next, v, u, &edge_count);
  }
//   printGraph(head, to, next, n);
  
  int longest = breath_first_search_algorithm(n, head, to, next);
  fprintf(stdout, "%d\n", (n - 1) * 2 - longest);
  return 0;
}

void addEdge(int* head, int* to, int* next, const int u, const int v, int* edge_count) {
  ++(*edge_count);
  *(next + *edge_count) = *(head + u);
  *(to + *edge_count) = v;
  *(head + u) = *edge_count;
}

int breath_first_search_algorithm(const int n, int* head, int* to, int* next) {
  
  SqQueue Q;
  InitQueue(&Q);
  EnQueue(&Q, 1);
    
  int seen[n + 1];
  memset(seen, 0x0000, sizeof seen);
  seen[1] = 1;
  
  int i, curr, steps = 0;
  while (NOT QueueEmpty(&Q)) {
    size_t s = QueueLength(&Q);
    while (s--) {
      DeQueue(&Q, &curr);
      for (i = head[curr]; i; i = next[i]) {
        int nei = *(to + i);
        if (*(seen + nei)) continue;
        EnQueue(&Q, nei);
        *(seen + nei) = 1;
      }
    }
    ++steps;
  }
  
  return DestroyQueue(&Q), steps - 1;
}

void printGraph(int* head, int* to, int* next, const int n) {
  int i, u;
  for (u = 1; u <= n; ++u) {
    fprintf(stdout, "vertex %d [ ", u);
    for (i = head[u]; i; i = next[i])
      fprintf(stdout, "%d ", to[i]);
    fputs("]\n", stdout);
  }
}

编辑于 2021-07-14 15:56:52 回复(0)
/*借用一下别人的代码,讲下思路: 其实就是每条边都会走两遍,一共有n-1条边,所以2*(n-1), 最后一条路径只需要走一次,
所以减去最后一条路径的长度。本质来说,就是求一个图的最长路径*/
#include <bits/stdc++.h>
usingnamespacestd;
constintN = 1e5+10;
vector<int> vec[N];
intans;
voiddfs(intx, intold, intw) {
    for(inti=0;i<vec[x].size();i++){
        if(vec[x][i]==old){
            continue;
        }
        dfs(vec[x][i],x,w+1);
    }
    ans = max(ans, w);
}
intmain() {
    intn;
    scanf("%d", &n);
    for(inti = 1; i < n; ++ i) {
        intx, y;
        scanf("%d%d", &x, &y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    ans = 0;
    dfs(1, -1, 0);
    printf("%d\n", (n-1)*2-ans);
    return0;
}

发表于 2019-05-09 12:06:28 回复(1)
用map构建无向图关系,使用bfs检索层数,借助队列实现
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Map<Integer,List<Integer>> map = new HashMap<>();
        for(int i=0;i<n-1;i++){
            int num1 = in.nextInt();
            int num2 = in.nextInt();
            if(map.get(num1)==null)
                map.put(num1,new ArrayList<Integer>());
            if(map.get(num2)==null)
                map.put(num2,new ArrayList<Integer>());
            map.get(num1).add(num2);
            map.get(num2).add(num1);
        }
        //bfs
        boolean[] flags = new boolean[n+1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        flags[1]=true;
        int res=-1;
        while(!queue.isEmpty()){
            int l = queue.size();
            for(int i=0;i<l;i++){
                int nu = queue.poll();
                List<Integer> tlist = map.get(nu);
                if(tlist==null)
                    continue;
                for(Integer num:tlist){
                    if(flags[num]==true)
                        continue;
                    flags[num]=true;
                    queue.offer(num);
                }
                    
            }
            res++;
        }
        System.out.println((n-1)*2-res);
    }
}



发表于 2021-06-21 19:11:50 回复(0)

由题意得:n个点,n-1条边组成得图是无环图,所以要遍历所有点,最少得走法是所有边走俩两边再减去图中得最长路径,所以本题可以理解为,用bfs求图得最长路径

from collections import defaultdict
d = defaultdict(list)
n = int(input())
for i in range(n-1):
    a,b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

visited = defaultdict(bool)
visited[1] = True
res = 0
stack = [1]
while len(stack) > 0:
    tmp = []
    while len(stack) > 0:
        t = stack.pop()
        for e in d[t]:
            if not visited[e]:
                visited[e] = True
                tmp.append(e)
    stack = tmp
    res += 1
print(2 * (n-1) - res + 1)
发表于 2019-08-23 16:29:01 回复(2)
我的理解是,首先这不是一个环,然后从1出发有好几条路径,所以要遍历所有的节点的话,假设有n条路径,n-1条路径都需要走来回两遍,所以最短路径就是最长的那条路径只走一边,其余的都走两遍。
发表于 2019-08-09 10:29:34 回复(2)
进一步推广到一般图中,由某点出发遍历图中所有节点所需的最短路程
结论:若图有N个节点,由该节点出发bfs遍历所得最大深度d,最短路程就是2*(N-1)-d
    原因:最短的路径,为沿最小生成树行走。每次到叶节点返回,在每个分支节点处都要经过两次。
          但注意到,如果某节点之前所有的子树都已经遍历过了,那么其与最后一个子树连接走一次即可。
          如此递归下去即有一条从根到叶子结点的路径只走了一次,那么只要使这条路径最长即可完成总路程最短的目标。
          显然在本题中,最长的路径就是图bfs得到的深度。而最小生成树总共有N-1条边,若树的深度为d,那么最短路程就是2*(N-1)-d。
    推广:对于一般的图,要想找到由某点出发遍历全图节点的最短路程。只需要首先找出该结点为根的最小生成树,
          再进一步寻找最寻找最小生成树中根到叶子结点的最长路径即可。
#include<iostream>
(720)#include<vector>
#include<queue>
(789)#include<algorithm>
#define N 100001
using namespace std;
int n,deg=0;
bool visit[N]={false};
vector<int> map[N];
int main()
{
    int x,y;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        cin>>x>>y;
        map[x].push_back(y);
        map[y].push_back(x);
    } 
    queue<int> Q;
	Q.push(1);
	int p,end=1,nend,adj;
	while(!Q.empty())
	{
		p=Q.front();
		visit[p]=true;
		//cout<<p<<' '<<data[p].degree<<endl;
		Q.pop();
		for(int i=0;i<map[p].size();i++)
		{
			adj=map[p][i];
			if(!visit[adj])
			{
				Q.push(adj);
				nend=adj;
			}
		}
		if(p==end) 
		{
			end=nend;
			deg++;	
		}
	}
	deg--;   
    
	cout<<2*(n-1)-deg;
		
    return 0;
}


发表于 2020-03-27 20:13:30 回复(0)
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    x, y = map(int, input().split(" "))
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
visited = [0 for _ in range(n)]
visited[0] = 1
# 从当前根节点开始到返回当前根节点的路程为2*(n-1),n为节点个数,即根节点的子节点个数的2倍
# 求树的深度
queue = [0]
depth = 0
while len(queue)>0:
    depth += 1
    size = len(queue)
    for _ in range(size):
        now = queue.pop(0)
        for j in edge[now]:
            if visited[j]==0:
                visited[j]=1
                queue.append(j)
print((n-1)*2-depth+1)

过了93.33%后超时了,还能怎么优化啊
发表于 2019-08-22 21:55:08 回复(7)
提交结果:答案错误 运行时间:1047ms 占用内存:60980KB 使用语言:Java 用例通过率:93.33%
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    static int max = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i=0; i<n-1; i++) {
            int key = in.nextInt();
            int val = in.nextInt();
            if (map.containsKey(key)) {
                List<Integer> list = map.get(key);
                list.add(val);
                map.put(key, list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(val);
                map.put(key, list);
            }
        }
        dfs(map, 1, 0);

        System.out.print(2*(n-1) - max);  
    }

    private static void dfs(HashMap<Integer, List<Integer>> map, int key, int num) {
        if (!map.containsKey(key)) {
            max = Math.max(max, num);
            return;
        }
        num++;
        for (Integer i : map.get(key)) {
            dfs(map, i, num);
        }        
    }
}



发表于 2023-04-20 21:13:55 回复(0)
其实就是寻找最长的路径,使用深度优先搜索
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

//使用深度优先搜索

const int MAXN=100002;
vector<int> matrix[MAXN];
//int num[MAXN];
int longer[MAXN];
bool flag[MAXN];

int dfs(int a)   //使用深度优先遍历a这个点下面的最长路径,
{
    for(int i=0;i<matrix[a].size();i++)
    {
        int x=matrix[a][i];
        
        if(flag[x])
        {  
            flag[x]=false;
             int l=dfs(x);
            flag[x]=true;
             if(l+1> longer[a])
             {  
                longer[a]=l+1;
             }
        }
       
    }
    return longer[a];
}

int main()
{
    int n;
    while(cin>>n)
    {
        //存储数据
        for(int i=0;i<n-1;i++)
        {
            int from, to;
            cin>>from>>to;
            matrix[from].push_back(to);
            matrix[to].push_back(from);
        }
        
        //初始化longer
        for(int i=0;i<=n;i++)
        {  longer[i]=0;
         flag[i]=true;
        }
        //深度优先搜索
        flag[1]=false;
        dfs(1);
         cout<<2*(n-1)-longer[1]<<endl;
 
    }
    return 0;
}


发表于 2022-05-10 10:13:27 回复(0)
为甚么超时??
public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<LinkedList<Integer>> list = new LinkedList();
        for(int i = 0; i < n; i++){
            list.add(new LinkedList<Integer>());
        }
        int[] visited = new int[n];
        for(int i = 0; i < n-1; i++){
            int f = sc.nextInt()-1;
            int e = sc.nextInt()-1;
            list.get(f).add(e);
            list.get(e).add(f);
        }
        int max_path = -1;
        //BFS
        Deque<Integer> queue = new LinkedList();
        queue.offerLast(0);
        visited[0] = 1;
        while(queue.size() > 0){
            int nums = queue.size();
            while(nums>0){
                int node = queue.pollFirst();    
                for(int i = 0; i < list.get(node).size(); i++){
                    int j = list.get(node).get(i);
                    if(visited[j]==0){
                        visited[j] = 1;
                        queue.offerLast(j);
                    }
                }
                nums--;
            }
            max_path++;
        }
        System.out.println(2*(n-1)-max_path);
    }

发表于 2021-03-16 23:39:27 回复(0)
这个题目其实就是求树的最大深度。节点数 × 2 - 最大深度就是答案。
发表于 2020-09-24 20:06:58 回复(0)
n = int(input())
path = {i: [] for i in range(n)}

for i in range(n-1):
    s, e = [int(i) - 1 for i in input().split()]
    
    path[s].append(e)
    path[e].append(s)

visited = [False] * n
stack = [0]
visited[0] = True
depth = 0

while stack:
    t = []
    while stack:
        node = stack.pop()
        for child in path[node]:
            if visited[child]:
                continue
            else:
                visited[child] = True
                t.append(child)
                
    stack = t
    if stack:
        depth += 1

print(2*(n-1) - depth)

发表于 2020-08-04 22:23:13 回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;
int main(){
    int N;
    cin>>N;
    vector<pair<int, int>> P(N-1);
    vector<vector<int>> matrix(N+1);
    for (int i = 0; i < N-1; ++i) {
        cin>>P[i].first>>P[i].second;
    }
    for (int i = 0; i < N-1; ++i) {
        matrix[P[i].first].push_back(P[i].second);
        matrix[P[i].second].push_back(P[i].first);
    }
    vector<bool> isVisted(N, false);
    queue<int> Q;
    isVisted[1] = true;
    Q.push(1);
    int num = 1;
    int level = 0;
    int count = 0;
    while(!Q.empty()){
        int val = Q.front();
        Q.pop();
        for (int i = 0; i < matrix[val].size(); ++i) {
            if(!isVisted[matrix[val][i]]) {
                Q.push(matrix[val][i]);
                isVisted[matrix[val][i]] = true;
                ++count;
            }
        }
        --num;
        if(num == 0){
            ++level;
            num = count;
            count = 0;
        }
    }
    cout<<2*(N-1)-level+1<<endl;
    return 0;
}


非递归的BFS
发表于 2020-06-08 10:53:23 回复(0)
递归实现深度优先搜索最终只能通过66.7%。
最后只能用广度优先搜索了,借助两个栈(不用栈也行,比如用队列,或者其他集合也可以)保存当前层节点和下一层节点,类似于求树的层数,其实一开始就想这么做,但还是习惯用dfs,没想到栈溢出。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

/**
 * @Author: coderjjp
 * @Date: 2020-05-10 20:05
 * @Description: 图的遍历--本题本质是求树的高度或者理解为从1出发的最长路径
 * @version: 1.0
 */
public class Main {
    static int len = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        for (int i = 1; i <= N; i++)
            graph.put(i, new ArrayList<>());
        String[] s;
        int num[] = new int[2];
        for (int i = 0; i < N - 1; i++){
            s = br.readLine().split(" ");
            num[0] = Integer.parseInt(s[0]);
            num[1] = Integer.parseInt(s[1]);
            graph.get(num[0]).add(num[1]);
            graph.get(num[1]).add(num[0]);
        }
        boolean flag[] = new boolean[N+1];
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> temp;
        stack.push(1);
        flag[1] = true;
        while (!stack.isEmpty()){
            temp = new Stack<>();
            while (!stack.isEmpty()){
                Integer pop = stack.pop();
                for (int son: graph.get(pop))
                    if (!flag[son]){
                        temp.push(son);
                        flag[son]=true;
                    }
            }
            if (!temp.isEmpty())
                len++;
            stack = temp;
        }
        System.out.println(2*(N-1) - len);
    }
}


编辑于 2020-05-10 22:21:23 回复(1)
#处理stack有两种方式,一是记录原来长度,切片
(3755)#二是直接把新元素添加给临时数组,直接赋值或者深拷贝
N = int(input())
edge = [[] for i in range(N)]
stack = []
for i in range(N-1):
    x, y = map(int,input().split())
    edge[x-1].append(y - 1)
    edge[y-1].append(x - 1)

visit = [False for i in range(N)]
visit[0] = True
stack.append(0)
depth = 1
while len(stack) > 0:
    temp = []
    flag = False
    while len(stack) > 0:
         i = stack.pop()
         for j in edge[i]:
            if visit[j]:
                    continue
            else:
                temp.append(j)
                visit[j] = True
                flag = True
        
    if flag:
        depth += 1
    stack = temp[:]
                
print(2 * N - 1 - depth)

发表于 2020-03-26 16:58:47 回复(0)
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean[] visit = new boolean[n+1];
		for(int i=0;i<n+1;i++)
			visit[i] = false;
		
		List<List<Integer>> map = new ArrayList<> ();
		for(int i=0;i<=n;i++) {
			List<Integer> lst = new ArrayList<Integer>();
			lst.add(i);
			map.add(lst);
		}
		for(int i=1;i<n;i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			List<Integer> lst = map.get(x);
			lst.add(y);
			lst = map.get(y);
			lst.add(x);
		}//graph
		
		
		class Element{
			int point;
			int deep;
			Element(int point, int deep){
				this.point = point;
				this.deep = deep;
			}
		}
		Queue<Element> queue = new LinkedList<>();
		Element e = new Element(1,0);
		visit[1] = true;
		int max = 0;
		queue.offer(e);
		while(!queue.isEmpty()) {
			Element temp = queue.poll();
			max=Math.max(max, temp.deep);
			List<Integer> lst = map.get(temp.point);
			for(int i=1;i<lst.size();i++) {
				if(!visit[lst.get(i)]) {
					visit[lst.get(i)]=true;
					queue.offer(new Element(lst.get(i),temp.deep+1));
				}
			}
		}
		int distance = 2*((n-1)-max)+max;
		System.out.println(distance);
	}
}

发表于 2020-03-19 15:45:01 回复(0)
package main

import (
	"fmt"
	"math"
)

var (
	sum    = 0
	v      = make(map[int][]int, N)
	visted = make(map[int]int, N)
	N      = 1000
)

func dfs(x int, w int) {
	for i := 0; i < len(v[x]); i++ {
		if visted[v[x][i]] == 0 {
			visted[v[x][i]] = 1
			dfs(v[x][i], w+1)
		}
	}
	sum = int(math.Max(float64(sum), float64(w)))
}

func main() {
	var a, b int
	fmt.Scanf("%d", &N)
	for i := 1; i <= N; i++ {
		visted[i] = 0
	}
	for i := 1; i <= N-1; i++ {
		fmt.Scanf("%d %d", &a, &b)
		v[a] = append(v[a], b)
		v[b] = append(v[b], a)
	}
	visted[1]=1
	dfs(1, 0)
	fmt.Println(2*(N-1) - sum)
}

编辑于 2020-03-13 00:16:10 回复(0)
93.3%,发生段错误,原因是输入的时候,当成i=0, i < n了!
发表于 2020-03-07 20:35:44 回复(1)

热门推荐

通过挑战的用户

查看代码