Cod sursa(job #2542605)

Utilizator Dragos1226Dragos Chileban Dragos1226 Data 10 februarie 2020 11:56:05
Problema Diametrul unui arbore Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");
const int NMax = 100000;
vector <int> G[NMax+5];

int N, Use[NMax+5], Lvl[NMax+5], maxi, nmax;

void Read() {
    in >> N;
    for (int i = 0,x,y; i < N-1; i++) {
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void DFS(int Node) {
    Use[Node] = 1;
    for (int i = 0; i < G[Node].size(); i++) {
        int Vecin = G[Node][i];
        if (!Use[Vecin]) {
            Lvl[Vecin] = Lvl[Node] + 1;
            if(Lvl[Vecin] > maxi)
                maxi = Lvl[Vecin], nmax = Vecin;
            DFS(Vecin);
        }
    }
}

int main() {
    Read();
    DFS(1);
    int cmaxi = maxi;
    DFS(nmax);
    out << cmaxi + maxi;
}