Cod sursa(job #2759117)

Utilizator lahayonTester lahayon Data 15 iunie 2021 15:54:30
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <map>
#include <unordered_map>
#include <queue>

using namespace std;

int bfs(int start, const vector<vector<int>>& graph, int op){

    vector<bool> visited(graph.size(), false);
    queue<pair<int, int>> Q;
    Q.push(pair<int, int>(start, 1));
    visited[start] = true;

    int current, d, maxd = 0;

    while(!Q.empty()){

        current = Q.front().first;
        d = Q.front().second;
        maxd = max(maxd, d);
        Q.pop();

        for(auto adjacent : graph[current])
            if(!visited[adjacent]){
                Q.push(pair<int, int>(adjacent, d + 1));
                visited[adjacent] = true;
                
            }
    }

    if(op == 0)
        return current;
    return maxd;
}

 
int main(){

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

int N;
cin >> N;
vector<vector<int>> graph(N, vector<int>({}));
for(int i = 0, x, y; i < N - 1; ++i){
    cin >> x >> y;
    graph[--x].push_back(--y);
    graph[y].push_back(x);
}

int last = bfs(0, graph, 0);
int result = bfs(last, graph, 1);

cout << result;

cin.close();
cout.close();
return 0;
}