Cod sursa(job #2591965)

Utilizator mihai03Mihai Grigore mihai03 Data 31 martie 2020 19:08:32
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
const int maxx = 100005;

int n;
vector < int > g[maxx];
vector < bool > seen;
void Read()
{
    fin >> n;
    for(int i = 1; i <= n - 1; i++)
    {
        int a, b;
        fin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    fin.close();
}

int nodmaxx, maxi;

void DFS(int k, int diametru)
{
    seen[k] = 1;
    if(diametru > maxi)
    {
        maxi = diametru;
        nodmaxx = k;
    }
    for(int i = 0; i < g[k].size(); i++)
    {
        if(seen[g[k][i]] == 0)
            DFS(g[k][i], diametru + 1);
    }
}

int main()
{
    Read();
    seen = vector < bool > (n + 1, 0);
    DFS(1, 0);
    seen = vector < bool > (n + 1, 0);
    DFS(nodmaxx, 0);
    fout << maxi + 1;
    return 0;
}