题目要求的是最远的两个节点的距离,即求树的直径(树中所有最短路径距离的最大值即为树的直径
求树的直径有两种做法,两次bfs(或者dfs),另一种是用树形DP
本文用两次DFS实现
#include<bits/stdc++.h> using namespace std; int n, u, v; vector<int> graph[50005]; vector<bool> visited(50005, false); int origin; void dfs(int p, int level, int & maximum) { visited[p] = true; bool isLeaf = true; for (auto i : graph[p]) { if (!visited[i]) { isLeaf = false; dfs(i, level + 1, maximum); } } if (isLeaf) { if (level > maximum) { origin = p; maximum = level; } } } int main() { cin >> n; for (int i = 1; i <= n; ++ i) { cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); } int maximum = INT32_MIN; //第一次dfs找到直径端点 dfs(1, 0, maximum); //初始化dfs所需参数 visited.clear(); visited.resize(n + 5, false); maximum = INT32_MIN; dfs(origin, 0, maximum); cout << maximum; }
标签:level,int,graph,maximum,dfs,BFS,DFS,visited,计蒜客 From: https://www.cnblogs.com/coderhrz/p/18535736