Cod sursa(job #2541112)

Utilizator AntoniuFicAntoniu Ficard AntoniuFic Data 8 februarie 2020 09:41:52
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n;
vector<int> muchii[100005];

pair<int, int> bfs(int start){
    bool viz[100005] = { 0 };
    int maxi = 0, maxes = 0;
    queue<pair<int, int>> deparc;
    deparc.push(make_pair(start, 1));
    while(!deparc.empty()) {
        int nod = deparc.front().first;
        int road = deparc.front().second;
        deparc.pop();
        viz[nod] = true;
        for (int i = 0; i < muchii[nod].size(); ++i) {
            if (!viz[muchii[nod][i]]){
                deparc.push(make_pair(muchii[nod][i], road + 1));
                if(road + 1 > maxi){
                    maxi = road + 1;
                    maxes = muchii[nod][i];
                }
            }
        }
    }
    return make_pair(maxes, maxi);
}

int main() {
    f>>n;
    for (int i = 0; i < n; ++i) {
        int x, y;
        f>>x>>y;
        muchii[x - 1].push_back(y - 1);
        muchii[y - 1].push_back(x - 1);
    }
    int nod = bfs(0).first;
    g<<bfs(nod).second;
    return 0;
}