Cod sursa(job #2797148)

Utilizator DayanamdrMardari Dayana Raluca Dayanamdr Data 9 noiembrie 2021 13:02:48
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <vector>
#include <utility>
#include <fstream>
using namespace std;

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

int n, leaves[100001];
vector<vector<int>> adjacentList(100001);

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

void initialize_array(int arr[100001], int element) {
    for (int i = 0; i <= n; ++i) {
        arr[i] = element;
    }
}

void dfs(int current_node, int visited[100001], pair<int, int> &furthestLeaf, int distance) {
    if (furthestLeaf.second < distance) {
        furthestLeaf.first = current_node; // update the node
        furthestLeaf.second = distance; // update the distance
    }
    for (int i = 0; i < adjacentList[current_node].size(); ++i) {
        int adjacentNode = adjacentList[current_node][i];
        if (!visited[adjacentNode]) {
            visited[adjacentNode] = 1;
            //nodes.push(adjacentNode)
            dfs(adjacentNode, visited, furthestLeaf, distance + 1);
        }
    }
}


int main() {
    f >> n;
    for (int i = 1; i < n; ++i) {
        int x, y;
        f >> x >> y;
        adjacentList[x].push_back(y);
        adjacentList[y].push_back(x);
        ++leaves[x];
        ++leaves[y];
    }
    int start_leaf = get_leaf();
    int visited[100001];
    initialize_array(visited, 0);
    pair<int, int> furthestLeaf (start_leaf, 1);
    visited[start_leaf] = 1;
    dfs(start_leaf, visited, furthestLeaf, 1);
    //cout << furthestLeaf.first << "  " << furthestLeaf.second << "\n";

    initialize_array(visited, 0);
    furthestLeaf.second = 1;
    dfs(furthestLeaf.first, visited, furthestLeaf, 1);
    g << furthestLeaf.second << "\n";

    return 0;
}