Cod sursa(job #1248500)

Utilizator gabrieligabrieli gabrieli Data 25 octombrie 2014 12:53:42
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <algorithm>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

vector<int> bfs(const int source, const vector<vector<int>>& G) {
    vector<int> D(G.size(), -1);
    queue<int> Q;
    
    for (Q.push(source), D[source] = 0; !Q.empty(); Q.pop())
        for (int v : G[Q.front()]) if (D[v] == -1) {
            D[v] = D[Q.front()] + 1;
            Q.push(v);
        }
    
    return D;
}

int main() {
    ifstream fin("darb.in");
    ofstream fout("darb.out");

    int n; fin >> n;
    vector<vector<int>> G(n);
    for (; n-1; --n) {
        int u, v;
        fin >> u >> v;
        G[u-1].push_back(v-1);
        G[v-1].push_back(u-1);
    }
    
    vector<int> D = bfs(0, G);
    int v = max_element(D.begin(), D.end()) - D.begin();
    
    D = bfs(v, G);
    int u = max_element(D.begin(), D.end()) - D.begin();
    
    fout << D[u] + 1 << endl;
    
    
    return 0;
}