Cod sursa(job #2819841)

Utilizator VladCaloVlad Calomfirescu VladCalo Data 19 decembrie 2021 11:41:02
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <cstring>
 
using namespace std;
 
ifstream fin ("darb.in");
ofstream fout ("darb.out");
 
 
vector<int> adj[100001];
int visited[100001];
int diam, nod_departe;
 
void DFS(int curr)
{
    for(int i = 0; i < adj[curr].size(); i++)
    {
        if(visited[adj[curr][i]] == 0)
        {
            visited[adj[curr][i]]=visited[curr];
            visited[adj[curr][i]]++;
            if(visited[adj[curr][i]] > diam)
            {
                nod_departe = adj[curr][i];
                diam=visited[adj[curr][i]];
            }
            DFS(adj[curr][i]);
        }
    }
}
 
int main()
{
    int n;
    fin>>n;
    for(int i=1; i<=n-1; i++)
    {
        int a,b;
        fin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    visited[1]=1;
    DFS(1);
    diam = 0;
    memset(visited,0,sizeof(visited));
    visited[nod_departe] = 1;
    DFS(nod_departe);
    fout <<diam;
    return 0;
}