Cod sursa(job #2199128)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 26 aprilie 2018 18:36:52
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define dimn 100005

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

int N, diam;
std::list <int> adj[dimn];
int nivel[dimn], last;
int root = 1;

std::queue <int> q;
void bfs(int t = 1, int index = root, int lvl = 0) {
    nivel[index] = lvl+t;
    q.push(index);

    while(!q.empty()) {
        index = q.front();
        q.pop();

        for (auto vec:adj[index])
            if(t*nivel[vec] <= 0) {
                q.push(vec);
                nivel[vec] = nivel[index] + t;
                diam = nivel[vec];
            }
        last = index;
    }
}

void citire() {
    f >> N;
    for (int i=0, x, y; i<N-1; i++) {
         f >> x >> y;
         adj[x].push_back(y);
         adj[y].push_back(x);
    }
}
void rezolvare() {
    bfs();
    bfs(-1, last);
    g << -diam << "\n";
}

int main()
{
    citire();
    rezolvare();

    return 0;
}