Cod sursa(job #2129503)

Utilizator CriogeniXBociat Daniel Tiberiu CriogeniX Data 12 februarie 2018 21:10:05
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 100005
using namespace std;
vector <int> L[Nmax];
queue <int> q;
int n,m,v[Nmax],con[Nmax],diametru,last;
ifstream fin ("darb.in");
ofstream fout ("darb.out");
void BFS (int nod)
{
    int x,i,vec;
    q.push(nod);
    for (i=1;i<=n;i++)
    {
        v[i]=0;
        con[i]=0;
    }
    v[nod]=1;
    con[nod]=1;
    while (!q.empty())
    {
        x=q.front();
        q.pop();
        for (i=0;i<L[x].size();i++)
        {
            vec=L[x][i];
            if (v[vec]==0)
            {
                q.push(vec);
                v[vec]=1;
                con[vec]=con[x]+1;


                diametru=con[vec];
                last=vec;
            }
        }
    }

}
int main()
{
    int i,x,y;
    fin>>n;
    for (i=1;i<n;i++)
    {
        fin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    BFS(1);
    BFS(last);
    fout<<diametru<<"\n";
    fin.close();
    fout.close();
    return 0;
}