Pagini recente » Cod sursa (job #3238452) | Cod sursa (job #3293688) | Cod sursa (job #3278120) | Cod sursa (job #3296911) | Cod sursa (job #3300452)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n;
vector<vector<int>> adj;
// 2 bfs
pair<int, int> bfs(int start) {
int max_node = 0, max_val = 0;
vector<int> d(n + 1, INT32_MAX);
queue<int> q;
q.push(start);
d[start] = 0;
while(!q.empty()) {
int node = q.front();
q.pop();
for (int neigh : adj[node])
if (d[node] + 1 < d[neigh]) {
d[neigh] = 1 + d[node];
q.push(neigh);
if (max_val < d[neigh]) {
max_val = d[neigh];
max_node = neigh;
}
}
}
return {max_node, max_val};
}
int longest_dag_bfs() {
auto [node, _] = bfs(1);
return 1 + bfs(node).second;
}
int main() {
fin >> n;
adj.resize(n + 1);
for (int x, y, i = 1; i < n; ++i) {
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
fout << longest_dag_bfs() << "\n";
}