Cod sursa(job #3282364)

Utilizator Barbu_MateiBarbu Matei Barbu_Matei Data 5 martie 2025 12:45:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> v[100001];
bool vis[100001];

pair<int, int> bfs(int head) {
    memset(vis, 0, sizeof(vis));
    queue<pair<int, int>> q;
    vis[head] = 1;
    q.push({head, 1});
    pair<int, int> last;
    while (!q.empty()) {
        int node = q.front().first;
        int len = q.front().second;
        last = {node, len};
        q.pop();
        for (int i = 0; i < v[node].size(); ++i) {
            if (!vis[v[node][i]]) {
                q.push({v[node][i], len + 1});
                vis[v[node][i]] = 1;
            }
        }
    }
    return last;
}

int main() {
    ifstream cin("darb.in");
    ofstream cout("darb.out");
    cin >> n;
    for (int i = 1; i <= n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
        vis[b] = 1;
    }
    int root = 0;
    for (int i = 1; i <= n; ++i) {
        if (vis[i] == 0) {
            root = i;
        }
    }
    int st = bfs(root).first;
    cout << bfs(st).second;
}