Cod sursa(job #2659576)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 17 octombrie 2020 10:22:49
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n;
int length[100100];
bool use[100100];
vector<vector<int>> adj;

void DFS(int node, int len)
{
    length[node] = len;
    use[node] = true;

    for(auto it: adj[node])
        if(!use[it])
            DFS(it, len + 1);
}

int main()
{
    in >> n;

    adj.resize(n + 5);

    for(int i = 1; i < n; i++)
    {
        int x, y;
        in >> x >> y;

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

    DFS(1, 0);

    int path1 = -1, path2 = -1, end1;

    for(int i = 1; i <= n; i++)
    {
        if(path1 < length[i])
        {
            path1 = length[i];
            end1 = i;
        }
    }

    for(int i = 1; i <= n; i++)
        if(i != end1)
            path2 = max(path2, length[i]);


    out << 1 + path1 + path2 << '\n';

    return 0;
}