Cod sursa(job #3200466)

Utilizator SIret_LucaSiret Luca SIret_Luca Data 4 februarie 2024 19:38:39
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector<int> graph[100001];

int n;

pair<int, int> BFS(int start) {
    vector<int> dist(n+1,-1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    int node, maxdist = 0, nod = start;
    while (!q.empty()) {
        node = q.front();
        q.pop();
        for (int next : graph[node]) {
            if (dist[next]==-1) {
                dist[next]=dist[node]+1;
                q.push(next);
                if (dist[next]>maxdist) {
                    maxdist=dist[next];
                    nod=next;
                }
            }
        }
    }

    return {nod, maxdist};
}

int main() {
    int i,a,b;
    fin>>n;
    for (i=1;i<n;++i) {
        fin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    pair<int,int>firstBFS=BFS(1);
    pair<int,int>secondBFS=BFS(firstBFS.first);
    fout<<secondBFS.second+1<<endl;
    fin.close();
    fout.close();
    return 0;
}