Cod sursa(job #3122890)

Utilizator alexlazuLazureanu Alexandru Ioan alexlazu Data 20 aprilie 2023 23:22:21
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

int n, best_dist = 0;

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

int dfs(vector<vector<int>> & adj, vector<int> &viz, int node) {
    int maxi1 = 0, maxi2 = 0;

    for (auto neigh : adj[node]) {
        if (!viz[neigh]) {
            viz[neigh] = viz[node] + 1;
            int dist = dfs(adj, viz, neigh);
            if (dist >= maxi1) {
                maxi2 = maxi1;
                maxi1 = dist;
            } else if (dist >= maxi2) {
                maxi2 = dist;
            }

            
        }
    }

    if (maxi1 + maxi2 + 1 > best_dist) {
        best_dist = maxi1 + maxi2 + 1;
    }

    return 1 + maxi1;
}


int main() {
    in >> n;

    vector <vector<int>> adj(n + 1, vector<int>());

    vector<int> viz(n + 1, 0);

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

    viz[1] = 0;

    dfs(adj, viz, 1);

    out << best_dist;
}