Cod sursa(job #2695189)

Utilizator albertyoAlbert Mindrescu albertyo Data 12 ianuarie 2021 00:26:33
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
#define N 100005

using namespace std;

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

int maxDepthNode, maxDistance;
vector <int> graf[N];
vector <bool> viz;

void dfs(int start, int diameter) {
    viz[start] = true;

    if(diameter > maxDistance) {
        maxDistance = diameter;
        maxDepthNode = start;
    }

    for(auto node : graf[start]) {
        if(!viz[node]) {
            dfs(node, diameter + 1);
        }
    }
}


int main() {
    int n;
    fin >> n;

    viz.resize(n + 1);

    for(int i = 1; i <= n - 1; i++) {
        int a, b;
        fin >> a >> b;

        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    dfs(1, 0);

    fill(viz.begin(), viz.end(), 0);
    dfs(maxDepthNode, 0);

    fout << maxDistance + 1;
}