Cod sursa(job #2843018)

Utilizator mediocrekarmaChirvasa George Matei mediocrekarma Data 1 februarie 2022 20:54:11
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include "pch.h"
using namespace std;

const int N_MAX = 1e5 + 1;
vector<int> v[N_MAX];

int bfs(int start, int &distance) {
    int dist[N_MAX] = {0};
    int last = -1;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        last = q.front();
        q.pop();
        for (int i = 0; i < v[last].size(); ++i) {
            if (!dist[v[last][i]]) {
                dist[v[last][i]] = dist[last] + 1;
                q.push(v[last][i]);
                distance = dist[v[last][i]];
            }
        }
    }
    return last;
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, distance;
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
    cout << bfs(1, distance) << '\n';
    cout << bfs(bfs(1, distance), distance) << '\n';
    cout << distance + 1;
}