Cod sursa(job #2797181)

Utilizator DayanamdrMardari Dayana Raluca Dayanamdr Data 9 noiembrie 2021 14:36:09
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <vector>
#include <utility>
#include <fstream>
using namespace std;

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

int n;
int is_leaf[100001];

struct node {
    int value;
    vector<int> adjacentNodes; // there will be stored maximum 3 nodes (2 children, 1 father)
    bool visited = false;
} nodes[100001];

int get_first_leaf() {
    for (int i = 1; i <= n; ++i) {
        if (is_leaf[i] == 1) {
            return i;
        }
    }
}

void dfs(int current_node, int distance, pair<int, int> &furthestLeaf) {
    if (distance > furthestLeaf.second) {
        furthestLeaf.first = current_node;
        furthestLeaf.second = distance;
    }
    nodes[current_node].visited = true;
    vector<int> children (nodes[current_node].adjacentNodes.begin(), nodes[current_node].adjacentNodes.end());
    for (int i = 0; i < children.size(); ++i) {
        int child = nodes[children[i]].value;
        if (nodes[child].visited == false) {
            dfs(child, distance + 1, furthestLeaf);
        }
    }
}

int main() {
    f >> n;
    for (int i = 1; i < n; ++i) {
        int x, y;
        f >> x >> y;
        nodes[x].value = x;
        nodes[y].value = y;
        nodes[x].adjacentNodes.push_back(y);
        nodes[y].adjacentNodes.push_back(x);
        ++is_leaf[x];
        ++is_leaf[y];
    }
    pair<int, int> furthestNLeaf (get_first_leaf(), 1); // first element it's the node, the second it's the distance

    dfs(furthestNLeaf.first, 1, furthestNLeaf);
    for (int i = 1; i <= n; ++i) {
        nodes[i].visited = false;
    }
    dfs(furthestNLeaf.first, 1, furthestNLeaf);
    g << furthestNLeaf.second << "\n";
    return 0;
}