Cod sursa(job #2500800)

Utilizator OvidRata Ovidiu Ovid Data 28 noiembrie 2019 18:18:44
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

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


bool k[100010];
int n;
vector<vector<int> > g;
vector<bool> v;
int m1, m0;

int dfs(int s){
   int m=1;
v[s]=true;
for(auto i=g[s].begin(); i!=g[s].end(); i++){
    
    if(!v[*i]){
    m=dfs(*i)+1;
    if(m>=m1){m0=m1; m1=m;} }

}
return m;
}




int main(){
fin>>n;

g.resize(n+5);
v.resize(n+5);

int n1, n2;

for(int i=1; i<n; i++){
fin>>n1>>n2;
k[n2]=true;
g[n1].pb(n2);
}

for(int i=1; i<=n; i++){
    if(!k[i]){n2=i;}
}

n1=dfs(n2);
fout<<(m1+m0-1)<<"\n";

    return 0;
}