Cod sursa(job #2541117)

Utilizator Vaida_Radu_AndreiVaida Radu Andrei Vaida_Radu_Andrei Data 8 februarie 2020 09:47:04
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <vector>
#include <queue>
#define VerticesMax 101024

using namespace std;

vector <int> Graph[VerticesMax];
int Vertices;

void read() {
    int I,V1,V2;
    scanf("%d",&Vertices);
    for(I=1;I<Vertices;++I) {
        scanf("%d%d",&V1,&V2);
        --V1;
        --V2;
        Graph[V1].push_back(V2);
        Graph[V2].push_back(V1);
    }
}

void mmset(int V[]) {
    int I;
    for(I=0;I<VerticesMax;++I) {
        V[I]=-1;
    }
}

void bfs(int StartingVertice,int&ResultVertice,int&ResultLength) {
    int Lengths[VerticesMax],I,Vert;
    queue<int>Q;
    Lengths[StartingVertice]=0;
    ResultLength=-1;
    mmset(Lengths);
    for(Q.push(StartingVertice);!Q.empty();Q.pop()) {
        Vert=Q.front();
        for(auto A:Graph[Vert]) {
            if(Lengths[A]<0) {
                Lengths[A]=Lengths[Vert]+1;
                Q.push(A);
                if(Lengths[A]>ResultLength) {
                    ResultLength=Lengths[A];
                    ResultVertice=A;
                }
            }
        }
    }
}

void solve() {
    int Vert,Length;
    bfs(0,Vert,Length);
    bfs(Vert,Vert,Length);
    printf("%d",Length+2);
}

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    read();
    solve();
    return 0;
}