Pagini recente » Cod sursa (job #3250584) | Cod sursa (job #2768109) | Cod sursa (job #178243) | Cod sursa (job #675491) | Cod sursa (job #1705203)
// FMI - UNIBUC - INFO
/*
_|_|_|_| _|_|_|_|_| _|_| _| _|_|_|_| _|_|_|_|_| _| _|_| _| _|_|_|_|_| _| _|_| _|
_| _| _| _| _| _| _| _| _| _| _| _| _| _| _| _| _| _|
_| _| _| _| _| _| _| _| _| _| _| _| _| _| _| _| _| _|
_| _| _| _| _| _| _|_|_| _| _| _|_|_| _| _| _| _| _| _| _| _|
_| _| _| _| _| _| _| _| _| _| _| _| _| _| _| _| _| _|
_|_|_|_| _|_|_|_|_| _| _|_| _|_|_|_| _| _| _| _| _|_| _| _| _| _|_|
*/
// Platform: Infoarena
// Problem: Diametrul unui arbore
// Programming Language: C++
// Date: 20.5.2016
# include <fstream>
# include <algorithm>
# include <cstring>
# include <vector>
# include <queue>
using namespace std;
ifstream f ( "darb.in" );
ofstream g ( "darb.out" );
int n, answer, d_max; // n - numarul de noduri, answer - ..., d_max - extremitate
int vec[100005]; // vector de distante
vector < int > v[100005]; // v - retinem arborele
queue < int > q; // coada pentru BFS
void distanta ( int start ) { // folosim BFS
memset( vec, 0, sizeof( vec ) );
answer = 0;
vec[start] = 1;
q.push( start );
while ( !q.empty() ) {
start = q.front(); // luam primul nod din coada
answer = vec[start];
q.pop(); // stergem nodul din coada
for ( int i = 0; i < v[start].size(); i ++ ) { // parcurgem vecinii nodului
if ( !vec[v[start][i]] ) { // daca nu a mai fost vizitat
vec[v[start][i]] = vec[start] + 1; // upddate distanta
q.push( v[start][i] ); // punem nodul in coada
}
}
}
d_max = start; // distanta maxima
}
int main()
{
f >> n;
for ( int i = 0; i < n - 1; ++ i ) {
int a, b; f >> a >> b;
v[a].push_back( b ); // retinem
v[b].push_back( a ); // graful
}
memset ( vec, 0, sizeof( vec ) );
distanta( n ); // ne ducem intr o exremitate a diametrului
memset ( vec, 0, sizeof( vec ) );
distanta( d_max ); // aflam diametrul
g << answer; // afisare
return 0;
}