时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 64M，其他语言128M
给定一张包含N个点、N-1条边的无向连通图，节点从1到N编号，每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点，那么总路程至少是多少？
输入描述:
第一行包含一个整数N，1≤N≤10^5。
接下来N-1行，每行包含两个整数X和Y，表示X号节点和Y号节点之间有一条边，1≤X，Y≤N。
输出描述:
输出总路程的最小值。
输入例子1:
4 1 2 1 3 3 4
输出例子1:
4
这道题很多人写过了，主要就是求根节点为1的树的深度的，最后结果是(n-1)*2-d。
但是我不想用递归写，所以就用BFS写了一次。
#include<bits/stdc++.h> using namespace std; int main() { int N; cin>>N; int visit[N]; for(int i=0;i<N;i++) visit[i]=0; vector<vector<int> > v1; queue<int> qu1; queue<int> qu2; for(int i=0;i<N;i++) v1.push_back(vector<int>()); for(int i=0;i<N-1;i++) { int a,b; cin>>a>>b; v1[a-1].push_back(b-1); v1[b-1].push_back(a-1); } int ans=0; qu1.push(0); while(!qu1.empty()) { while(!qu2.empty()) qu2.pop(); while(!qu1.empty()) { int a=qu1.front(); qu1.pop(); visit[a]=1; for(int i=0;i<v1[a].size();i++) { int b=v1[a][i]; if(!visit[b]) { qu2.push(b); } } } ans++; qu1=qu2; } cout<<N*2-1-ans; return 0; }
需要注意的是ans多算了一次，所以最后要减去一次。
原文链接: https://www.cnblogs.com/xiachongyubing/p/12662106.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/340776
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
