Cod sursa(job #2309415)

Utilizator AndreiLunguLungu Andrei Sebastian AndreiLungu Data 28 decembrie 2018 23:28:12
Problema Diametrul unui arbore Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#define N 100004
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int pr , n , d[N] , c[N] , viz[N];
vector <int> L[N];
queue <int> q;
void Citire()
{
    int x , y;
    fin >> n;
    while(fin >> x >> y)
    {
        L[x].push_back(y);
        L[y].push_back(x);
    }
    fin.close();
}
void Bfs(int nod)
{
    int i;
    d[nod] = 1;
    viz[nod] = 1;
    q.push(nod);
    while(!q.empty())
    {
        i = q.front();
        q.pop();
        for(auto j : L[i])
            if(viz[j] == 0)
            {
                d[j] = d[i] + 1;
                viz[j] = 1;
                q.push(j);
            }
    }
}
int main()
{
    int i , mx;
    Citire();
    Bfs(1);
    pr = 1;
    for(i = 2; i <= n; i++)
        if(d[i] > d[pr])
            pr = i;
    memset(viz , 0 , N);///pune 0 peste tot in viz de la 1 la N
    memset(d , 0 , N);
    Bfs(pr);
    mx = -1;
    for(i = 1; i <= n; i++)
        if(d[i] > mx)mx = d[i];
    fout << mx << "\n";
    return 0;
}