Cod sursa(job #2672412)

Utilizator MevasAlexandru Vasilescu Mevas Data 13 noiembrie 2020 21:35:40
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>

using namespace std;

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

int maxDepthNode, maxDistance;
vector<int> graf[100001];
vector<bool> visited;

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

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

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


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

    visited.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);
//    Resetam vectorul de noduri vizitate pentru dfs-ul de la nodul cel mai adanc
    fill(visited.begin(), visited.end(), 0);
    dfs(maxDepthNode, 0);

    fout << maxDistance + 1;
}