Cod sursa(job #2007935)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 4 august 2017 16:36:24
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
int n,i,x,y,p,u,maxim,val,vecin,v[100001],c[100001],last,diametru;
vector <int> L[100001];
ifstream fin ("darb.in");
ofstream fout ("darb.out");
void bfs (int nod){
    int p=1,u=1;
    c[1] = nod;
    v[nod] = 1;
    while (p <= u){
        for (int i=0;i<L[c[p]].size();i++){
            int vecin = L[c[p]][i];
            if (v[vecin] == 0){
                u++;
                c[u] = vecin;
                v[vecin] = 1 + v[c[p]];

                diametru = v[vecin];
                last = L[c[p]][i];
            }
        }

        p++;
    }

}
int main (){

    fin>>n;
    for (i=1;i<n;i++){
        fin>>x>>y;
        L[x].push_back (y);
        L[y].push_back (x);
    }
    for (i=1;i<=n;i++)
        sort (L[i].begin(),L[i].end());
    // facem bfs din nodul 1
    bfs (1);
    for (i=1;i<=n;i++)
        v[i] = 0;
    bfs (last);
    //diametru = 0;
    //for (i=1;i<=n;i++)
      //  diametru = max (diametru,v[i]);
    fout<<diametru;

    return 0;
}