Cod sursa(job #2600223)

Utilizator CharacterMeCharacter Me CharacterMe Data 12 aprilie 2020 12:11:13
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

int n, dmax, node;
int dist[100005];
vector<int> graph[100005];
queue<int> que;

void bfs(int start);

int main()
{

    fin >> n;
    for(int i = 1; i < n; ++i){
        int x, y;
        fin >> x >> y;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    bfs(1);
    bfs(node);

    fout << dmax;

    return 0;
}

void bfs(int start){
    dmax = 0;
    for(int i = 1; i <= n; ++i) dist[i] = 0;

    dist[start] = 1;
    que.push(start);
    while(!que.empty()){
        int now = que.front(); que.pop();
        if(dist[now] > dmax){
            dmax = dist[now];
            node = now;
        }

        for(auto next:graph[now]){
            if(dist[next]) continue;

            dist[next] = dist[now] + 1;
            que.push(next);
        }
    }
}