Pagini recente » Cod sursa (job #1515747) | Cod sursa (job #1539704) | Cod sursa (job #2836419) | Cod sursa (job #889467) | Cod sursa (job #2736938)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
#define Nmax 100002
#define INF 100002
vector<int> graph[Nmax];
int d[Nmax];
queue <int> q;
int n; // numarul de noduri al arborelui
void bfs(int s) {
int i, x, y;
// initializare vector d
for (i = 1; i <= n; i++) {
d[i] = INF;
}
// inserez nodul sursa in coada
q.push(s);
d[s] = 0;
while (!q.empty()) {
x = q.front(); // extrag nodul de la inceputul cozii
q.pop(); // eliminare nod de la inceputul cozii
// parcurg vecinii nodului x
for (i = 0; i < graph[x].size(); i++) {
y = graph[x][i];
if (d[y] > d[x] + 1) {
// actualizare distanta
d[y] = d[x] + 1;
// inserare in coada vecin y
q.push(y);
}
}
}
}
int main()
{
int i, x, y;
in >> n;
for (i = 0; i < n - 1; i++) {
in >> x >> y;
// graf neorientat
graph[x].push_back(y);
graph[y].push_back(x);
}
bfs(1);
// for (i = 1; i <= n; i++) {
// cout << d[i] << " ";
// }
// cout << '\n';
int dist_max = d[1];
int pos_dist_max = 1;
for (i = 2; i <= n; i++) {
if (d[i] > dist_max) {
dist_max = d[i];
pos_dist_max = i;
}
}
// cout << dist_max << '\n';
// cout << pos_dist_max << '\n';
bfs(pos_dist_max);
// for (i = 1; i <= n; i++) {
// cout << d[i] << " ";
// }
// cout << '\n';
int diametru = d[1];
for (i = 1; i <= n; i++) {
if (d[i] > diametru) {
diametru = d[i];
}
}
out << diametru + 1 << '\n';
return 0;
}