Pagini recente » Cod sursa (job #16561) | Cod sursa (job #2821528) | Cod sursa (job #1296612) | Cod sursa (job #1291203) | Cod sursa (job #2244128)
#include <bits/stdc++.h>
using namespace std;
vector <int> graff [100001];
int cost[100001];
int n, last;
int BFS(int start, int &secondStart){
queue <int> qq;
qq.push(start);
for (int i = 1; i <= n; i ++){
cost[i] = (1 << 29);
}
cost[start] = 0;
while (!qq.empty()){
int frontValue = qq.front();
qq.pop();
for (auto vecin : graff[frontValue]){
if ( cost[vecin] > cost[frontValue] + 1){
cost[vecin] = cost[frontValue] + 1;
qq.push(vecin);
last = vecin;
}
}
}
int maxim = -2;
for (auto &x : cost){
if ( x == (1 << 29)){
cost[x] = -1;
}
if ( x > maxim){
maxim = x;
}
}
secondStart = maxim + secondStart;
return last;
}
int main() {
ifstream f("darb.in");
ofstream g("darb.out");
int start;
f >> n;
for (int i = 1; i <= n - 1; i++){
int x, y;
f >> x >> y;
graff[x].push_back(y);
graff[y].push_back(x);
if ( i == 1){
start = x;
}
}
int secondStart;
BFS(start, secondStart);
// g << secondStart << " ";
BFS(last, start);
g << start;
return 0;
}