Pagini recente » Cod sursa (job #44591) | Cod sursa (job #1714629) | Cod sursa (job #57751) | Cod sursa (job #811948) | Cod sursa (job #1890176)
/*
Diametrul unui arbore
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define MAXN 100000 + 4
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
vector<int> graph[MAXN];
queue<int> coada;
queue<int> depth;
bool visited[MAXN];
int n, x, y, ff, maxdist;
void bfs(int start){
memset(visited, 0, sizeof(visited));
while(!coada.empty())
coada.pop();
coada.push(start);
depth.push(1);
while(!coada.empty()){
if(depth.front()>maxdist){
maxdist = depth.front();
ff = coada.front();
}
for(unsigned int i=0;i<graph[coada.front()].size();i++){
if(!visited[graph[coada.front()][i]]){
visited[graph[coada.front()][i]] = 1;
coada.push(graph[coada.front()][i]);
depth.push(depth.front()+1);
}
}
coada.pop();
depth.pop();
}
}
int main()
{
in>>n;
for(int i=0;i<n;i++){
in>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
bfs(1);
bfs(ff);
out<<maxdist;
return 0;
}