Cod sursa(job #1488587)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 19 septembrie 2015 11:50:22
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <queue>
#include <vector>

#define NMAX 100007

using namespace std;

int Viz[NMAX], n, Max, Next;
queue < int > q;
vector < int > v[NMAX];

void bfs(int Node){
    q.push(Node);
    for(int i = 1; i <= n; ++i)
        Viz[i] = 0;
    Viz[Node] = 1;
    while(! q.empty()){
        Node = q.front();
        q.pop();
        for(vector < int > :: iterator it = v[Node].begin(); it != v[Node].end(); ++it)
            if(Viz[*it] == 0){
                Viz[*it] = Viz[Node] + 1;
                if(Viz[*it] > Max){
                    Max = Viz[*it];
                    Next = *it;
                }
                q.push(*it);
            }
    }
}

int main(){
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        int A, B;
        scanf("%d %d", &A, &B);
        v[A].push_back(B);
        v[B].push_back(A);
    }
    bfs(1);
    bfs(Next);
    printf("%d", Max);
    return 0;
}