Cod sursa(job #3206912)

Utilizator Iustin2812Ion Iustin Ciprian Iustin2812 Data 24 februarie 2024 13:52:54
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 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[100001]={0};
int maxdist[100001];
int dp[100001];
vector <int> l[100001];

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(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;
    /*cin>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }*/
    while(fin>>x>>y){
        l[x].push_back(y);
        l[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        maxdist[i]=1;
        dp[i]=1;
    }
        
    dfs(1);
    int maxi=0;
    for(int i=1;i<=n;i++)
        if(maxi<dp[i])
            maxi=dp[i];
    fout<<maxi;
    return 0;
}