Cod sursa(job #2632736)

Utilizator marius004scarlat marius marius004 Data 4 iulie 2020 16:50:49
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 100'001;

int n, beenThere[NMAX] , depth[NMAX] , dist[NMAX];
vector <int> ARB[NMAX];

void Read() {

    f >> n;

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

void dfs(int node) {

    beenThere[node] = 1;

    for (int neighbor : ARB[node]) {
        if (!beenThere[neighbor]) {
            depth[neighbor] = 1 + depth[node];
            dfs(neighbor);
        }
    }
}

void bfs(const int& startNode) {

    dist[startNode] = 1;
    
    vector<bool> vis(n + 1,false);
    queue <int> q;

    q.push(startNode);
    vis[startNode] = 1;

    while(!q.empty()) {

        int node = q.front();
        q.pop();

        for(int neighbor : ARB[node]) {
            if (!vis[neighbor]) {
                vis[neighbor] = 1;
                dist[neighbor] = 1 + dist[node];
                q.push(neighbor);
            }
        }
    }
}

void print() {
    
    int sol{};
    
    for(int i = 1;i <= n;++i)
        if(dist[i] > sol)
            sol = dist[i];
    
    g << sol << '\n';
}

void solve() {

    dfs(1);

    int max_depth_node {};
    for(int i = 1;i <= n;++i)
        if(depth[i] > depth[max_depth_node])
            max_depth_node = i;

   bfs(max_depth_node);
}

int main() {

    Read();
    solve();
    print();

    return 0;
}