Cod sursa(job #3138091)

Utilizator Vasilescu_CosminVasilescu Cosmin Vasilescu_Cosmin Data 17 iunie 2023 13:10:14
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include <map>
#include <queue>

#define INF 1e9
#define MOD 1e9 + 7
using namespace std;

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

void solve();

int32_t main() {
//    ios::sync_with_stdio(false);
//    cin.tie(NULL);
//    cout.tie(NULL);
    int t;
//    cin >> t;
    t = 1;
    while (t--) {
        solve();
    }
}

pair<int,int> findFurthest(int start,vector<vector<int>>adjMap, vector<bool>viz){
    int maxnode1 = 1;
    int maxdist = 0;

    queue<pair<int,int>>q;
    q.emplace(start,0);

    while (!q.empty()){
        pair<int,int> p = q.front();
        q.pop();
        int curNode = p.first;
        int curDist = p.second;
        viz[curNode] = true;
        if(curDist>maxdist){
            maxdist = curDist;
            maxnode1 = curNode;
        }

        for(int neighbor : adjMap[curNode]){
            if(!viz[neighbor])
                q.emplace(neighbor,curDist+1);
        }
    }
    return make_pair(maxnode1, maxdist);
}

void solve() {
    int n;
    in>>n;
    vector<vector<int>>adjMap(n+5);
    vector<bool>viz(n+1, false);
    for(int i=1; i<=n-1;i++){
        int a,b;
        in>>a>>b;
        adjMap[a].push_back(b);
        adjMap[b].push_back(a);
    }

    pair<int,int>p1 = findFurthest(1, adjMap,viz);
    for(int i=1; i<=n;i++)
        viz[i]=false;
    pair<int,int>p2 = findFurthest(p1.first,adjMap,viz);

    out<<1+p2.second;
}