Cod sursa(job #2659577)

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

using namespace std;

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

int n, x, path = -1;
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);

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

    memset(use, false, sizeof use);
    memset(length, 0, sizeof length);

    DFS(x, 1);

    path = -1;

    for(int i = 1; i <= n; i++)
        path = max(path, length[i]);

    out << path << '\n';

    return 0;
}