Cod sursa(job #2376465)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 8 martie 2019 15:50:16
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <vector>
#include <fstream>
#include <cstring>

#define NMAX 100010
using std::vector;

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

int n;
vector<int> ad[NMAX];

int dpthMax, nodeMax;
bool vis[NMAX];

void dfs(int node, int dpth) {
    vis[node] = true;
    if (dpth > dpthMax) {
        dpthMax = dpth;
        nodeMax = node;
    }

    for (int nghb : ad[node])
        if (!vis[nghb])
            dfs(nghb, dpth + 1);
}

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

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

    dpthMax = 0;
    memset(vis, false, sizeof(vis));
    dfs(1, 1);

    dpthMax = 0;
    memset(vis, false, sizeof(vis));
    dfs(nodeMax, 1);

    fout << dpthMax << '\n';
    fout.close();
    return 0;
}