Pagini recente » Cod sursa (job #934883) | Cod sursa (job #1487748) | Cod sursa (job #1476735) | Cod sursa (job #2133245) | Cod sursa (job #3229971)
#include <bits/stdc++.h>
using namespace std;
class Task {
public:
void solve() {
read_input();
int diameter = get_diameter();
print_output(diameter);
}
private:
int n;
vector<vector<int>> adj;
void read_input() {
ifstream fin("darb.in");
fin >> n;
adj.resize(n + 1);
for (int i = 0; i < n - 1; ++i) {
int a, b;
fin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
fin.close();
}
pair<int, int> bfs(int start) {
vector<int> dist(n + 1, -1);
queue<int> q;
q.push(start);
dist[start] = 0;
int farthest_node = start;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
q.push(neighbor);
if (dist[neighbor] > dist[farthest_node]) {
farthest_node = neighbor;
}
}
}
}
return {farthest_node, dist[farthest_node]};
}
int get_diameter() {
pair<int, int> first_bfs = bfs(1);
pair<int, int> second_bfs = bfs(first_bfs.first);
return second_bfs.second + 1;
}
void print_output(int diameter) {
ofstream fout("darb.out");
fout << diameter << endl;
fout.close();
}
};
int main() {
auto* task = new (nothrow) Task();
if (!task) {
return -1;
}
task->solve();
delete task;
return 0;
}