Cod sursa(job #2049290)

Utilizator DianaVelciovVelciov Diana DianaVelciov Data 27 octombrie 2017 00:14:43
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int N_MAX = 1e5 + 5;
vector<int> G[N_MAX];
int N, str[N_MAX], D[N_MAX], maxim = 0;
queue <int> Q;

void bfs(){
    while(!Q.empty()){
        int a = Q.front(); Q.pop();
        for (int vecin : G[a]){
            if(D[vecin] == -1){
                D[vecin] = D[a] + 1;
                Q.push(vecin);
                str[vecin] = str[a];
            }
            else {
                D[vecin] = max(D[vecin], D[a] + 1);
            }
            if(str[vecin] != str[a]){
                maxim = max(D[vecin] + D[a] + 1, maxim);
            }
        }
    }

}
int main(){
    in >> N ;
    for(int i = 1; i < N; ++i){
        int x, y; in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for (int i = 1; i <= N; ++i)
        D[i] = -1;
    for (int i = 1; i <= N; ++i)
        if (G[i].size() == 1){
            Q.push(i);
            str[i] = i;
            D[i] = 0;
        }
    bfs();
    out << maxim <<'\n';
    in.close(); out.close();
    return 0;
}