Cod sursa(job #3207017)

Utilizator alexandraiacobelAlexandra Iacob alexandraiacobel Data 24 februarie 2024 18:49:34
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

const int Nmax = 100005;
vector <int> L[Nmax];
int darb, niv_max, nivel,capat,viz[Nmax];

void dfs(int nod)
{
    nivel++;
    viz[nod] =1;
    for(int i=0;i<L[nod].size();i++)
    {
        int vec = L[nod][i];
        if(!viz[vec])
            dfs(vec);
    }
    if(nivel > niv_max) niv_max = nivel, capat = nod; //capat este primul capat gasit al lantului;
    nivel--;
}
int main()
{
    int n,i,j;
    fin>>n;
    for(i=1; i<n;i++)
    {
        int a,b;
        fin>>a>>b;
        L[a].push_back(b);
        L[b].push_back(a);
    }
    // Diametrul unui arbore este este suma a 2 cele mai lungi brate

    //din oricare nod, voi cauta cel mai lung brat. Iar apoi din frunza celui mai lung rbat voi cauta lantul
	dfs(1);
	for(i=1;i<=n;i++) viz[i] = 0;
	dfs(capat);
	darb = niv_max;
	fout<<darb;
	return 0;
}