Cod sursa(job #2723503)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 14 martie 2021 12:40:27
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <stdio.h>
#include <vector>

using namespace std;

void dfs(
    int node, int prev_node, int distance,
    vector<vector<int> > & tree, int & max_distance, int & furthest
) {
    // leaf node
    if (
        (tree[node].size() == 0) ||
        (tree[node].size() == 1 && tree[node][0] == prev_node)
    ) {
        if (distance > max_distance) {
            max_distance = distance;
            furthest = node;
        }
        return;
    }

    for (int neighbor: tree[node]) {
        if (neighbor == prev_node) {
            continue;
        }
        dfs(neighbor, node, distance + 1, tree, max_distance, furthest);
    }
}

int main() {
    FILE * f;
    int n, a, b;

    f = fopen("darb.in", "r");
    fscanf(f, "%d", &n);
    vector<vector<int> > tree(n);
    for (int i = 0; i < n - 1; ++i) {
        fscanf(f, "%d%d", &a, &b);
        --a;
        --b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    fclose(f);

    int max_distance = 1, furthest = 0;
    dfs(0, -1, 1, tree, max_distance, furthest);
    dfs(furthest, -1, 1, tree, max_distance, furthest);

    f = fopen("darb.out", "w");
    fprintf(f, "%d", max_distance);
    fclose(f);

    return 0;
}