Pagini recente » Cod sursa (job #335778) | Cod sursa (job #290248) | Cod sursa (job #1969874) | Cod sursa (job #2063542) | Cod sursa (job #1671690)
#include <iostream>
#include <vector>
#include<queue>
#include<fstream>
using namespace std;
int n, m, s;
vector<vector <int> > graph;
vector<int> visited;
vector <int> grad;
struct info
{
int d,elem;
};
int bfs (int vertex)
{
queue <info> q;
info element;
info aux;
aux.d=0;
aux.elem=vertex;
q.push(aux);
visited[vertex]=0;
info v;
int u;
while(!q.empty())
{
element=q.front();
for(int i=0;i<graph[element.elem].size();i++)
{
if(visited[graph[element.elem][i]]==-1)
{
aux.d=1+element.d;
aux.elem=graph[element.elem][i];
q.push(aux);
visited[graph[element.elem][i]]=aux.d;
}
}
v=q.back();
u=v.elem;
q.pop();
}
return u;
}
int main()
{
int n;
ifstream f("darb.in");
ofstream g("darb.out");
f>>n;
graph.resize(n);
visited.resize(n,-1);
grad.resize(n,0);
for(int i=1;i<n;i++)
{
int x ,y;
f>>x>>y;
x--;
y--;
grad[x]++;
grad[y]++;
graph[x].push_back(y);
graph[y].push_back(x);
}
int u;
for(int i=0;i<n;i++)
{
if(grad[i]==1)
{
u=bfs(i);
visited.clear();
visited.resize(n,-1);
int v;
v=bfs(u);
g<<visited[v]+1;
break;
}
}
f.close();
g.close();
return 0;
}