Cod sursa(job #2645914)

Utilizator ursu2001Ursu Ianis-Vlad ursu2001 Data 30 august 2020 00:38:09
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;

int N;
vector<vector<int>> tree;


//first - leaf id
//second - distance
pair<int, int> furthest_leaf(int starting_node)
{
    vector<int> visited(N + 1, false);
    vector<int> dist(N + 1, 0);
    queue<int> Q;

    Q.push(starting_node);
    visited.at(starting_node) = true;

    pair<int, int> answer = {starting_node, dist.at(starting_node)};

    while(Q.empty() == false)
    {
        int node = Q.front();
        Q.pop();

        if(answer.second < dist.at(node)) answer = {node, dist.at(node)};

        for(int& next : tree[node])
        {
            if(visited.at(next) == true) continue;

            visited.at(next) = true;
            dist.at(next) = dist.at(node) + 1;
            Q.push(next);
        }
    }

    return answer;

}


int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");

    fin >> N;

    tree.resize(N + 1, vector<int>());

    for(int i = 1; i < N; ++i)
    {
        int x, y;
        fin >> x >> y;

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

    fout << furthest_leaf(furthest_leaf(1).first).second + 1;
}