Cod sursa(job #3167725)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 11 noiembrie 2023 00:57:31
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 1e5 + 1;

vector<int> G[NMAX];

int max(int a, int b) {
    return a > b ? a : b;
}

int compute_longest_path(int node) {
    int longest_path = 0;
    for (int i = 0; i < (int)G[node].size(); i++) {
        int next_node = G[node][i];
        longest_path = max(longest_path, compute_longest_path(next_node));
    }
    return longest_path + 1;
}

int main()
{
    FILE *fin, *fout;
    fin = fopen("darb.in", "r");
    fout = fopen("darb.out", "w");

    int n, x, y;
    fscanf(fin, "%d", &n);
    for (int i = 0; i < n - 1; i++) {
        fscanf(fin, "%d %d", &x, &y);
        G[x].push_back(y);
    }
    
    int max1, max2, longest_path;
    max1 = max2 = 0;
    for (int i = 0; i < (int)G[1].size(); i++) {
        longest_path = compute_longest_path(G[1][i]);
        if (longest_path >= max1) {
            max2 = max1;
            max1 = longest_path;
        } else if (longest_path >= max2) {
            max2 = longest_path;
        }
    }
    fprintf(fout, "%d\n", max1 + max2 + 1);

    fclose(fin);
    fclose(fout);
    return 0;
}