Cod sursa(job #1112451)

Utilizator Theorytheo .c Theory Data 19 februarie 2014 19:35:42
Problema Diametrul unui arbore Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

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

const int NMAX = 10009;

int N;

vector<int> G[NMAX]; bool viz[NMAX]; int dist[NMAX]; int head;

void bfs(int start) {

    queue<int> Q;
    Q.push(start);
    viz[start] = true;
    while(!Q.empty()) {

        int nod = Q.front();
        Q.pop();

        for(unsigned i = 0 ;i < G[nod].size(); ++i) {
            if(viz[G[nod][i]] == false) {
                Q.push(G[nod][i]);
                dist[G[nod][i]] = dist[nod] + 1;
                viz[G[nod][i]] = true;

                if(dist[head] < dist[G[nod][i]])
                    head = G[nod][i];
            }
        }
    }

}

int main() {

    fin >> N;
    for(int i = 2; i <= N; ++i) {

        int A; int B; fin >> A >>B;
        G[A].push_back(B);
        G[B].push_back(A);
    }

    bfs(1);
    memset(dist, 0, sizeof(dist));
    memset(viz, false, sizeof(viz));

    bfs(head);

    fout << dist[head] + 1<< '\n';

    return 0;
}