Cod sursa(job #3324704)

Utilizator zionlyismAdobroaiei David zionlyism Data 23 noiembrie 2025 10:35:37
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>

#define NMAX 100002
using namespace std;

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

int n;
vector<vector<int>> graf;

bool vizitat[NMAX];

void citire();

int diametru(int nod);
void DFS(int nod, int dist);
int distmax, nod_distmax;

int main()
{
    citire();
    fout<<diametru(1)<<'\n';
    return 0;
}

void citire()
{
 int x, y, i;
 fin>>n;
 graf.resize(n + 2);
 for(i = 1; i <= n - 1; i++)
 {
     fin>>x>>y;
     graf[x].push_back(y);
     graf[y].push_back(x);
 }
}

int diametru(int nod)
{
 distmax = 0;
 DFS(nod, 1);
 for(int i = 1; i <= n; i++) vizitat[i] = 0;
 DFS(nod_distmax, 1);
 return distmax;
}

void DFS(int nod, int dist)
{
 int i;
 vizitat[nod] = 1;
 if(dist > distmax)
 {
    distmax = dist; nod_distmax = nod;
 }
 for(i = 0; i < graf[nod].size(); i++)
    if(!vizitat[graf[nod][i]])
    {
       DFS(graf[nod][i], dist + 1);
    }
}