Pagini recente » Borderou de evaluare (job #1247025) | Borderou de evaluare (job #2126133) | Borderou de evaluare (job #872913) | Borderou de evaluare (job #2834720) | Cod sursa (job #2854905)
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <deque>
#include <vector>
#include <set>
#include <queue>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
const int MAX_SIZE = 500005;
vector<int> graph[MAX_SIZE];
int diameter = 0, lastPeak = 0;
void findMaximumDistances(int startPeak) {
int distances[MAX_SIZE];
memset(distances, -1, MAX_SIZE);
distances[startPeak] = 1;
queue<int> positions;
positions.push(startPeak);
while (!positions.empty()) {
int currentPeak = positions.front();
positions.pop();
if (1 == graph[currentPeak].size()) {
lastPeak = currentPeak;
}
for (int i = 0; i < graph[currentPeak].size(); ++i) {
int nextPeak = graph[currentPeak][i];
if (distances[nextPeak] == -1) {
distances[nextPeak] = distances[currentPeak] + 1;
diameter = max(diameter, distances[nextPeak]);
positions.push(nextPeak);
}
}
}
}
int main() {
int peaks;
fin >> peaks;
for (int i = 1; i <= peaks - 1; ++i) {
int start, end;
fin >> start >> end;
graph[end].push_back(start);
graph[start].push_back(end);
}
findMaximumDistances(1);
findMaximumDistances(lastPeak);
fout << diameter;
return 0;
}