Pagini recente » Cod sursa (job #1095914) | Cod sursa (job #122464) | Cod sursa (job #2334409) | Cod sursa (job #1381862) | Cod sursa (job #2954841)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("darb.in");
ofstream cout("darb.out");
const int NMAX = 1e5;
const int inf = 1e9;
vector <int> g[NMAX + 1];
queue <int> q;
int d[NMAX + 1], n;
void bfs(int x){
d[x] = 0;
q.push(x);
while(!q.empty()){
int nc = q.front();
q.pop();
for(auto y : g[nc]){
if(d[y] > d[nc] + 1){
d[y] = d[nc] + 1;
q.push(y);
}
}
}
}
int main(){
cin >> n;
for(int i = 0; i < n - 1; i++){
int x = 0, y = 0;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1; i <= n; i++)
d[i] = inf;
bfs(1); // bfs dintr-un nod oarecare
int nod = 0, dist = 0;
// caut cel mai indepartat nod de nodul oarecare (1)
for(int i = 1; i <= n; i++)
if(d[i] > dist)
nod = i, dist = d[i];
for(int i = 1; i <= n; i++)
d[i] = inf;
bfs(nod); // bfs din cel mai indepartat nod de nodul oarecare (1)
int dmax = 0;
for(int i = 1; i <= n; i++)
if(d[i] > dmax)
dmax = d[i];
cout << dmax + 1; // prin "distanta", ei s-au referit in problema la numarul de noduri ale lantului de lungime maxima (=diametru). Un lant
// cu n noduri are n - 1 muchii. Noi am gasit, de fapt, numarul de muchii ale lantului de lungime maxima, deci va trebui
// sa adaugam 1 la rezultat (dmax), pentru a afisa numarul de NODURI ale lantului de lungime maxima.
// dmax reprezinta, de fapt, numarul de muchii ale lantului (adica n - 1)
// dmax = n - 1 / + 1
// <=> dmax + 1 = n = distanta ceruta
return 0;
}