Cod sursa(job #3152392)

Utilizator not_anduAndu Scheusan not_andu Data 24 septembrie 2023 21:37:53
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
/**
 * Author: Andu Scheusan (not_andu)
 * Created: 24.09.2023 21:29:58
*/

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define INFILE "darb.in"
#define OUTFILE "darb.out"

#define all(x) (x).begin(), (x).end()
#define MP make_pair
#define F first
#define S second

typedef long long ll;

const int VMAX = 100002;

int n;
vector<int> adj[VMAX];
int dist[VMAX];
bool viz[VMAX];

void bfs(int source){

    memset(viz, false, sizeof viz);
    memset(dist, 0x3f3f3f3f, sizeof dist);

    dist[source] = 0;

    queue<int> q;

    q.push(source);

    while(!q.empty()){

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

        for(int i = 0; i < adj[node].size(); ++i){

            int to = adj[node][i];

            if(!viz[to] && to != source){

                dist[to] = dist[node] + 1;
                viz[to] = true;

                q.push(to);

            }

        }

    }

}

void solve(){

    cin >> n;

    for(int i = 0; i < n - 1; ++i){

        int node1, node2;

        cin >> node1 >> node2;

        adj[node1].push_back(node2);
        adj[node2].push_back(node1);

    }

    bfs(1);

    int nrMaxim = 0;
    int distMax = 0;

    for(int i = 1; i <= n; ++i){

        if(dist[i] > distMax){

            distMax = dist[i];
            nrMaxim = i;

        }

    }

    bfs(nrMaxim);

    distMax = 0;

    for(int i = 1; i <= n; ++i){

        distMax = max(distMax, dist[i]);

    }

    cout << distMax + 1 << '\n';

}

int main(){
    
    ios_base::sync_with_stdio(false);

    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);

    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}