Cod sursa(job #2855307)

Utilizator CiuiGinjoveanu Dragos Ciui Data 22 februarie 2022 12:03:39
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>
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();
        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;
}