Cod sursa(job #2670686)

Utilizator Harsa_AndreiHarsa Andrei Harsa_Andrei Data 10 noiembrie 2020 15:16:51
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

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

bool viz[100002];
int d[100002], maxim;
list<int> M[100002];

void DFS(int k)
{
    for(int x : M[k])
        if(!viz[x])
        {
            viz[x] = true;
            d[x] = d[k] + 1;
            if(d[maxim] < d[x])
                maxim = x;
            DFS(x);
        }
}

int main()
{
    int n, x, y;

    fin >> n;

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

    viz[1] = true;
    DFS(1);

    for(int i = 1; i <= n; i++)
    {
        d[i] = 0;
        viz[i] = false;
    }

    viz[maxim] = true;
    DFS(maxim);

    fout << d[maxim] + 1;
    return 0;
}