Pagini recente » Borderou de evaluare (job #1729307) | Cod sursa (job #2706505) | Borderou de evaluare (job #522012) | Cod sursa (job #466270) | Cod sursa (job #3233266)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>
using namespace std;
vector<int> adj[100001];
int dist[100001];
pair<int, int> bfs(int start, int n) {
queue<int> q;
q.push(start);
memset(dist, -1, sizeof(dist));
dist[start] = 0;
int farthest_node = start;
int max_dist = 0;
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] > max_dist) {
max_dist = dist[neighbor];
farthest_node = neighbor;
}
}
}
}
return {farthest_node, max_dist};
}
int main() {
ifstream infile("darb.in");
ofstream outfile("darb.out");
int n;
infile >> n;
for (int i = 0; i < n - 1; ++i) {
int u, v;
infile >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Prima parcurgere BFS
pair<int, int> first_bfs = bfs(1, n);
// A doua parcurgere BFS
pair<int, int> second_bfs = bfs(first_bfs.first, n);
// Diametrul arborelui
outfile << second_bfs.second << endl;
infile.close();
outfile.close();
return 0;
}