Cod sursa(job #2575574)

Utilizator FrostfireMagirescu Tudor Frostfire Data 6 martie 2020 14:28:20
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define NMAX 100000

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

int n, dist[NMAX+10], p;
bool viz[NMAX+10];
vector <int> nod[NMAX+10];
queue <int> Q;

void bfs(int x)
{   memset(viz, 0, sizeof(viz));
    memset(dist, 0, sizeof(dist));
    viz[x] = 1;
    Q.push(x);
    while(!Q.empty())
        {   int a = Q.front();
            Q.pop();
            for(int i=0; i<nod[a].size(); i++)
                if(!viz[nod[a][i]])
                    {   dist[nod[a][i]] = dist[a] + 1;
                        viz[nod[a][i]] = 1;
                        Q.push(nod[a][i]);
                    }
        }
}

int main()
{
    f >> n;
    for(int i=1; i<n; i++)
        {   int nod1, nod2;
            f >> nod1 >> nod2;
            nod[nod1].push_back(nod2);
            nod[nod2].push_back(nod1);
        }
    bfs(1);
    int maxi = 0;
    for(int i=1; i<=n; i++) if(dist[i] > maxi) maxi = dist[i], p = i;
    bfs(p);
    maxi = 0;
    for(int i=1; i<=n; i++) if(dist[i] > maxi) maxi = dist[i];
    g << maxi+1 << '\n';
    return 0;
}