You are viewing a single comment's thread. Return to all comments →
#include <iostream> #include <vector> #include <queue> using namespace std; vector<vector<int>> tree; vector<int> dist; void bfs(int start, int &farthest) { queue<int> q; q.push(start); dist[start] = 0; while (!q.empty()) { int node = q.front(); q.pop(); for (int neighbor : tree[node]) { if (dist[neighbor] == -1) { dist[neighbor] = dist[node] + 1; q.push(neighbor); if (dist[neighbor] > dist[farthest]) farthest = neighbor; } } } } int longestPath(int n) { dist.assign(n + 1, -1); int farthest = 1; bfs(1, farthest); dist.assign(n + 1, -1); bfs(farthest, farthest); return dist[farthest]; } int main() { int n, u, v; cin >> n; tree.assign(n + 1, vector<int>()); for (int i = 0; i < n - 1; i++) { cin >> u >> v; tree[u].push_back(v); tree[v].push_back(u); } cout << longestPath(n); return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
"Hello World!" in C
You are viewing a single comment's thread. Return to all comments →