B4016 樹的直徑 - 洛谷

題目描述

給定一棵 n 個結點的樹，樹沒有邊權。請求出樹的直徑是多少，即樹上最長的不重復經過一個點的路徑長度是多少。

輸入格式

第一行輸入一個正整數 n，表示結點個數。
第二行開始，往下一共 n - 1 行，每一行兩個正整數 (u, v)，表示一條邊。

輸出格式

輸出一行，表示樹的直徑是多少。

輸入輸出樣例

輸入 #1	輸出 #1
5 1 2 2 4 4 5 2 3	3

說明/提示

數據保證，1≤n≤1e5

代碼：

#include<bits/stdc++.h>
using namespace std;
int n, start, step; 
vector<int> G[100000];  void dfs(int cur, int fa, int cnt) {if (cnt > step) {start = cur;step = cnt;}for (auto to : G[cur]) {  if (to == fa) continue;dfs(to, cur, cnt + 1);}
}int main() {cin >> n;for (int i = 1; i < n; i++) { int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u); }dfs(1, -1, 0);step = 0; dfs(start, -1, 0);cout << step << endl;return 0;
}