图的遍历

#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;
}

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);
    }

}

#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);
  }
}

	 



	/*借用一下别人的代码，讲下思路： 其实就是每条边都会走两遍，一共有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;



	}

由题意得：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)

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)

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);
    }

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)

#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;
}

#处理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)

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);
	}
}

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)
}