Cod sursa(job #3230284)

Utilizator cristianc90210Cristian Constantin cristianc90210 Data 20 mai 2024 13:56:50
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
//
// Created by Cristian Constantin on 20.05.2024.
//
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100001;

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

vector<int> adj[MAXN];
int n, maxDist, farthestNode;
int visited[MAXN];

void readInput() {
    fin >> n;
    int x, y;
    for (int i = 0; i < n - 1; ++i) {
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}

void dfs(int node) {
    for (int neighbor : adj[node]) {
        if (visited[neighbor] == 0) {
            visited[neighbor] = visited[node] + 1;
            dfs(neighbor);
        }
    }
}

void findFarthestNode() {
    maxDist = 0;
    for (int i = 1; i <= n; ++i) {
        if (visited[i] > maxDist) {
            maxDist = visited[i];
            farthestNode = i;
        }
    }
    fill(visited, visited + n + 1, 0);
    visited[farthestNode] = 1;
}

int main() {
    readInput();

    visited[1] = 1;
    dfs(1);

    findFarthestNode();
    dfs(farthestNode);

    maxDist = 0;
    for (int i = 1; i <= n; ++i) {
        maxDist = max(maxDist, visited[i]);
    }

    fout << maxDist << endl;

    return 0;
}