Cod sursa(job #2695781)

Utilizator @stefansevastre@Stefan Sevastre @stefansevastre@ Data 14 ianuarie 2021 15:05:10
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int N_MAX = 1e5 + 1;

vector <int> graph[N_MAX];
vector <int> visitedCost;


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

void DFS(int node)
{
    for(auto neighbor: graph[node])
    {
        if(visitedCost[neighbor] == -1)
        {
            visitedCost[neighbor] = visitedCost[node] + 1;
            DFS(neighbor);
        }
    }
}

int main()
{
    int n;

    fin >> n;

    visitedCost.resize(n + 1);
    fill(visitedCost.begin(), visitedCost.end(), -1);

    for(int i = 0, st, dr; i < n; i++)
    {
        fin >> st >> dr;
        graph[st].push_back(dr);
        graph[dr].push_back(st);
    }

    visitedCost[1] = 1;
    DFS(1);

    int maxDistanceNodeFromFirst = distance(visitedCost.begin(), max_element(visitedCost.begin(), visitedCost.end()));
    fill(visitedCost.begin(), visitedCost.end(), -1);
    visitedCost[maxDistanceNodeFromFirst] = 1;
    DFS(maxDistanceNodeFromFirst);

    int maxDistance = *max_element(visitedCost.begin(), visitedCost.end());
    fout << maxDistance;
    return 0;
}