Cod sursa(job #2852795)

Utilizator CiuiGinjoveanu Dragos Ciui Data 19 februarie 2022 16:16:05
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
s#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;
 
void findMaximumDistances(int start) {
    queue<int> positions;
    positions.push(start);
    int distance = 1;
    while (!positions.empty()) {
        int currentPeak = positions.back();
        positions.pop();
        for (int i = 0; i < graph[currentPeak].size(); ++i) {
            positions.push(graph[currentPeak][i]);
            ++distance;
        }
    }
    maximums[++noMax] = distance;
}
 
int main() {
    int peaks;
    cin >> peaks;
    for (int i = 1; i <= peaks - 1; ++i) {
        int start, end;
        cin >> start >> end;
        graph[end].push_back(start);
    }
    for (int i = 1; i <= peaks; ++i) {
        findMaximumDistances(i);
    }
    sort(1 + maximums, 1 + maximums + noMax);
    cout << maximums[noMax - 1] + maximums[noMax] - 1;
    return 0;
}