Cod sursa(job #2244128)

Utilizator pinteastefanPintea Teodor Stefan pinteastefan Data 22 septembrie 2018 11:41:47
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> graff [100001];
int cost[100001];
int n, last;

int BFS(int start, int &secondStart){
    queue <int> qq;
    qq.push(start);
    for (int i = 1; i <= n; i ++){
        cost[i] = (1 << 29);
    }
    cost[start] = 0;
    while (!qq.empty()){
        int frontValue = qq.front();
        qq.pop();
        for (auto vecin : graff[frontValue]){
            if ( cost[vecin] > cost[frontValue] + 1){
                cost[vecin] = cost[frontValue] + 1;
                qq.push(vecin);
                last = vecin;
            }
        }
    }
    int maxim = -2;
    for (auto &x : cost){
        if ( x == (1 << 29)){
            cost[x] = -1;
        }
        if ( x > maxim){
            maxim = x;
        }
    }
    secondStart = maxim + secondStart;
    return last;
}

int main() {
    ifstream f("darb.in");
    ofstream g("darb.out");
    int start;
    f >> n;
    for (int i = 1; i <= n - 1; i++){
        int x, y;
        f >> x >> y;
        graff[x].push_back(y);
        graff[y].push_back(x);
        if ( i == 1){
            start = x;
        }
    }
    int secondStart;
    BFS(start, secondStart);
    //  g << secondStart << " ";
    BFS(last, start);
    g << start;
    return 0;
}