Cod sursa(job #2854893)

Utilizator CiuiGinjoveanu Dragos Ciui Data 21 februarie 2022 20:26:28
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb

#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


*/