Cod sursa(job #2547607)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 15 februarie 2020 15:08:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAX 100000

using namespace std;

vector< int >graph[MAX + 5];
int depthMax1, depthMax2, depthMaxNod;

void dfs1(int nod, int dad, int depth)
{
    if(depth > depthMax1)
    {
        depthMax1 = depth;
        depthMaxNod = nod;
    }

    for(auto son : graph[nod])
    {
        if(son == dad)continue;

        dfs1(son, nod, depth + 1);
    }
}

void dfs2(int nod, int dad, int depth)
{
    if(depth > depthMax2)
        depthMax2 = depth;

    for(auto son : graph[nod])
    {
        if(son == dad)continue;

        dfs2(son, nod, depth + 1);
    }
}

int main()
{
    int n;

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

    fin >> n;

    for(int cnt = 0; cnt < n; cnt++)
    {
        int a, b;

        fin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs1(1, 0, 1);
    dfs2(depthMaxNod, 0, 1);

    fout << depthMax2 << '\n';

    fin.close();
    fout.close();

    return 0;
}