Pagini recente » Rating Katarina Stavros (satalmaty) | Monitorul de evaluare | Rating Martinescu Rares (Rares1) | Cod sursa (job #2048488) | Cod sursa (job #2645914)
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> tree;
//first - leaf id
//second - distance
pair<int, int> furthest_leaf(int starting_node)
{
vector<int> visited(N + 1, false);
vector<int> dist(N + 1, 0);
queue<int> Q;
Q.push(starting_node);
visited.at(starting_node) = true;
pair<int, int> answer = {starting_node, dist.at(starting_node)};
while(Q.empty() == false)
{
int node = Q.front();
Q.pop();
if(answer.second < dist.at(node)) answer = {node, dist.at(node)};
for(int& next : tree[node])
{
if(visited.at(next) == true) continue;
visited.at(next) = true;
dist.at(next) = dist.at(node) + 1;
Q.push(next);
}
}
return answer;
}
int main()
{
ifstream fin("darb.in");
ofstream fout("darb.out");
fin >> N;
tree.resize(N + 1, vector<int>());
for(int i = 1; i < N; ++i)
{
int x, y;
fin >> x >> y;
tree[x].push_back(y);
tree[y].push_back(x);
}
fout << furthest_leaf(furthest_leaf(1).first).second + 1;
}