Cod sursa(job #3248618)

Utilizator vlad_binVlad Bintintan vlad_bin Data 12 octombrie 2024 11:35:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

#ifdef INFOARENA
ifstream in("darb.in");
ofstream out("darb.out");
#else
#define in cin
#define out cout
#endif

vector<vector<int>> graph;
int max_depth = 0;
int max_depth_node;
vector<bool> visited;
bool first = true;

void dfs(int node, int depth = 0) {
    if (visited[node]) return;
    visited[node] = true;

    if (graph[node].size() == 1 && !first) {
        if (depth > max_depth) {
            max_depth = depth;
            max_depth_node = node;
        }
        return;
    }

    first = false;

    for (int child : graph[node]) {
        dfs(child, depth + 1);
    }
}

int main() {
    int n;
    in >> n;
    graph.resize(n+1);
    visited.resize(n+1);

    for (int i = 1; i < n; i++) {
        int x, y;
        in >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    dfs(1);
    for (unsigned i = 0; i < visited.size(); i++) {
        visited[i] = false;
    }
    first = true;
    dfs(max_depth_node);

    out << max_depth + 1 << '\n';
    
}