Cod sursa(job #2392595)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 30 martie 2019 10:56:48
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

const int NMAX = 100000;

int N;
int dist[NMAX];
vector <int> g[NMAX + 5];

void DFS(int node, int d)
{
    dist[node] = d;

    for(auto it : g[node])
        if(!dist[it])
            DFS(it, d + 1);
}

int main()
{
    fin >> N;

    int x, y;
    for(int i = 1; i <= N; i++)
    {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    DFS(1, 1);

    int maxDist = 0, maxDistNode = -1;

    for(int i = 1; i <= N; i++)
        if(dist[i] > maxDist)
        {
            maxDist = dist[i];
            maxDistNode = i;
        }

    memset(dist, 0, sizeof(dist));

    DFS(maxDistNode, 1);

    maxDist = 0;

    for(int i = 1; i <= N; i++)
        maxDist = max(maxDist, dist[i]);

    fout << maxDist;

    return 0;
}