Cod sursa(job #3206898)

Utilizator Iustin2812Ion Iustin Ciprian Iustin2812 Data 24 februarie 2024 13:35:08
Problema Diametrul unui arbore Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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


int n,m;
int x,y;
int viz[101]={0};
int maxdist[101];
int dp[101];
vector <int> l[101];

void dfs(int node){
    viz[node]=1;
    for(int i:l[node]){
        if(viz[i]==0){
            dfs(i);
        }
    }
    
    int maxi1=0,maxi2=0,maxdp=0;
    for(int i:l[node]){
        if(maxi1<maxdist[i])
            maxi1=maxdist[i];
        if(maxi1>maxdist[i]&&maxi2<maxdist[i])
            maxi2=maxdist[i];
        if(maxdp<dp[i])
            maxdp=dp[i];
    }
    
    if(maxi1==0&&maxdp==0){
        maxdist[node]=1;
        dp[node]=1;
    }
    else{
        if(maxdp>maxi1+maxi2+1){
            dp[node]=maxdp;
            maxdist[node]=maxi1+1;
        }
        else{
            dp[node]=maxi1+maxi2+1;
            maxdist[node]=maxi1+1;
        }
    }

}

int main(){
    
    fin>>n;
    while(fin>>x>>y){
        l[x].push_back(y);
        l[y].push_back(x);
    }
    dfs(1);
    int maxi=0;
    for(int i=1;i<=n;i++)
        if(maxi<dp[i])
            maxi=dp[i];
    fout<<maxi;
    return 0;
}