Cod sursa(job #2570309)

Utilizator Antonio020712Potra Antonio Antonio020712 Data 4 martie 2020 16:02:46
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 100005

using namespace std;

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

int n, dMax, nodMax;
bool vizitat[NMAX];
vector<int> g[NMAX];

void citire() {
    int i, x, y;

    fin >> n;
    for (i = 1; i < n; i++) {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void dfs(int nod, int dist) {
    int i, vecin;

    if (dist > dMax) {
        dMax = dist;
        nodMax = nod;
    }

    vizitat[nod] = true;
    for (i = 0; i < g[nod].size(); i++) {
        vecin = g[nod][i];
        if (vizitat[vecin] == false)
            dfs(vecin, dist + 1);
    }
}

int main() {
    citire();
    dfs(1, 0);
    dMax = 0;
    memset(vizitat, false, n);
    dfs(nodMax, 0);

    fout << dMax + 1;

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

    return 0;
}