Cod sursa(job #3250051)

Utilizator ioanabaduIoana Badu ioanabadu Data 19 octombrie 2024 09:51:36
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");

int nodes;
vector <int> graph[100005];
int viz[100005];

int dfs (int x){
    viz[x] = true;

    int ans = 0;
    for (auto idx:graph[x])
        if (viz[idx] == false)
            ans = max(ans, dfs(idx));
    
    return ans + 1;
}

int main (){
    int x, y;

    in >> nodes;
    for (int i=1; i<nodes; ++i){
        in >> x >> y;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    int best1 = 0, best2 = 0;
    viz[1] = true; // nu conteaza ce root aleg ca tot aia e
    for (auto idx:graph[1]){
        int current = dfs(idx);

        if (current > best1){
            best2 = best1;
            best1 = current;
        }
        else if (current > best2){
            best2 = current;
        }
    }

    out << best1 + best2 + 1;


    return 0;
}