Pagini recente » Cod sursa (job #408720) | Cod sursa (job #1755671) | Cod sursa (job #1275136) | Cod sursa (job #1626841) | Cod sursa (job #2853533)
#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 = 100005;
vector<int> graph[MAX_SIZE];
int maximums[MAX_SIZE], noMax = 0;
int result = 0;
int lastPeak = 0;
void findMaximumDistances(int start) {
int distances[MAX_SIZE];
memset(distances, -1, MAX_SIZE);
distances[start] = 0;
queue<int> positions;
positions.push(start);
int maximum = 0;
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;
maximum = max(maximum, distances[nextPeak]);
positions.push(nextPeak);
}
}
}
result = max(result, maximum);
}
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 << result + 1;
return 0;
}
/*
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10 -> 18 NU
11
1 2
1 3
1 4
2 5
3 6
4 7
5 8
5 9
6 10
10 11 -> 8 ok
12
11 1
1 2
2 4
11 10
10 3
3 7
11 9
9 5
5 12
5 6
11 8 -> 7 ok
*/