Pagini recente » Borderou de evaluare (job #2566378) | Cod sursa (job #1706767)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
vector < vector<int> > graph;
vector <bool> visited;
vector <int> cost;
ifstream f("darb.in");
ofstream g("darb.out");
int n,last,diam;
void bfs(int vertex)
{
if(vertex < 0 || vertex>n) return;
int element;
queue<int> q;
q.push(vertex);
visited[vertex]=true;
cost[vertex]=1;
while(!q.empty())
{
element=q.front();
for(int i=0; i<graph[element].size();i++)
if(!visited[graph[element][i]])
{
q.push(graph[element][i]);
cost[graph[element][i]]=cost[element]+1;
visited[graph[element][i]]=true;
diam=cost[graph[element][i]];
last=graph[element][i];
}
q.pop();
}
}
int main()
{
int a,b;
f>>n;
graph.resize(n+1);
cost.resize(n+1, 0);
visited.resize(n+1,false);
for(int i=0;i<n-1;i++){
f>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
bfs(1);
cost.clear();
visited.clear();
bfs(last);
g<<diam;
return 0;
}