题解 | #MT44 图的遍历#(BFS+哈希表+转化思想)

解题思路

1.除了最长的路径,所有的路径均需要走两遍,使用转化思想,将问题转化为两遍路径(2 * (n - 1))-最长路径(step)即可;

代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    while(cin >> n){
        unordered_map<int, vector<int>> f; //n-1条边无向连通图,不可能有环
        int u, v;
        for(int i = 0; i < n - 1; i++){
            cin >> u >> v;
            f[u].push_back(v);
            f[v].push_back(u);
        }
        queue<int> q;
        vector<bool> isVisited(n + 1);
        q.push(1);
        isVisited[1] = true;
        int curSize, step = -1;
        while(!q.empty()){ //除了最长的路径,所有的路径均需要走两遍 两遍路径(2 * (n - 1))-最长路径(step)
            curSize = q.size(); 
            step++;
            for(int i = 0; i < curSize; i++){
                int node = q.front();
                q.pop();
                if(f.count(node) == 0) continue;
                for(auto& e : f[node]){
                    if(isVisited[e]) continue;
                    q.push(e);
                    isVisited[e] = true;
                }
            }
        }
        cout << 2 * (n - 1) - step << endl;
    }
    return 0;
}