Cod sursa(job #2876621)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 23 martie 2022 12:43:40
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

int n;

int depth[100001];

vector < int > adj[100001];

void dfs(int node)
{
    for (auto it : adj[node])
        if (!depth[it])
        {
            depth[it] = depth[node] + 1;
            dfs(it);
        }
}

int main()
{
    f >> n;

    for (int i = 1; i <= n - 1; i++)
    {
        int x, y; f >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    memset(depth, 0, sizeof(depth));
    depth[1] = 1;
    dfs(1);

    int node1 = 0, depth1 = 0;
    for (int i = 1; i <= n; i++)
        if (depth[i] > depth1)
        {
            node1 = i;
            depth1 = depth[i];
        }

    memset(depth, 0, sizeof(depth));
    depth[node1] = 1;
    dfs(node1);

    int node2 = 0, depth2 = 0;
    for (int i = 1; i <= n; i++)
        if (depth[i] > depth2)
        {
            node2 = i;
            depth2 = depth[i];
        }

    g << depth2 << "\n";

    return 0;
}