Cod sursa(job #3138072)

Utilizator sygAndreiIonitaIonita Andrei sygAndreiIonita Data 17 iunie 2023 12:39:31
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

vector<int>v[100001];
queue<int>q,r;
bool ok[100001];
int dist[100001],dist2[100001];

int main() {
    int n,a,b;
    in>>n;
    for (int i=1;i<=n-1;i++) 
        in>>a>>b,v[a].push_back(b),v[b].push_back(a);
    q.push(1);
    int maxx=0,secnode;
    ok[1]=1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int node : v[x]) 
            if (!ok[node]) {
                ok[node]=1,dist[node]=dist[x]+1,q.push(node);
                if (dist[node]>maxx)
                    maxx=dist[node],secnode=node; 
            }
    }
    r.push(secnode);
    int maxx2=0;
    ok[secnode]=0;
    while (!r.empty()) {
        int x = r.front();
        r.pop();
        for (int node : v[x])
            if (ok[node]) {
                ok[node]=0,dist2[node]=dist2[x]+1,r.push(node);
                maxx2=max(maxx2,dist2[node]);
            }
    }
    out<<maxx2+1;
    return 0;
}