Pagini recente » Cod sursa (job #1700878) | Cod sursa (job #1754731) | Cod sursa (job #1052519) | Cod sursa (job #1082264) | Cod sursa (job #2854893)
#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 result = 0;
int lastPeak = 0;
void findMaximumDistances(int start) {
int distances[MAX_SIZE];
memset(distances, -1, MAX_SIZE);
distances[start] = 1;
queue<int> positions;
positions.push(start);
int maximum = 0;
while (!positions.empty()) {
int currentPeak = positions.front();
positions.pop();
if (1 == graph[currentPeak].size() && distances[currentPeak] == maximum) {
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;
return 0;
}
/*
TESTE:
8
1 2
2 3
2 4
2 5
1 4
1 7
1 8 -> 4
7
2 7
1 2
1 3
1 4
1 5
1 6 -> 4
6
1 2
1 3
1 4
1 5
1 6 -> 3
2
2 1 -> 2
9
1 3
3 2
3 4
4 5
5 6
6 7
6 8
8 9 -> 7
8
1 8
8 2
8 3
3 4
4 6
3 5
5 7 -> 5
8
3 1
3 2
6 5
3 6
7 6
4 7
1 8 -> 6
7
3 1
3 2
6 5
3 6
7 6
4 7 -> 5
4
3 2
2 4
1 2 -> 3
3
2 1
2 3 -> 3
11
11 10
1 10
3 1
3 2
3 8
8 9
3 4
4 5
4 6
6 7 -> 7
13
1 2
2 9
1 4
4 11
11 12
11 13
1 5
1 6
1 7
7 8
1 3
3 10 -> 6
11
1 3
3 6
6 10
10 11
1 2
2 5
5 8
5 9
1 4
4 7 -> 8
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10 -> 10
11
1 2
1 3
1 4
2 5
3 6
4 7
5 8
5 9
6 10
10 11 -> 8
12
11 1
1 2
2 4
11 10
10 3
3 7
11 9
9 5
5 12
5 6
11 8 -> 7
*/