Cod sursa(job #1630527)

Utilizator AdrianGotcaAdrian Gotca AdrianGotca Data 5 martie 2016 09:55:04
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

int n,dmax;
vector < vector <int> > G;
vector <int> d;
void read();
void DFS(int,int);
void solve();
void write();
int main(){
    read();
    solve();
    write();
    return 0;
}

void read(){
    freopen("darb.in","r",stdin);
    scanf("%d",&n);
    G.assign(n+1,vector <int> ());
    d.assign(n+1,0);
    for (int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void solve(){
    DFS(1,1);
    d.assign(n+1,0);
    DFS(dmax,1);
}

void write(){
    int dmax=0;
    for (int i=1;i<=n;i++){
        dmax=max(dmax,d[i]);
    }
    freopen("darb.out","w",stdout);
    printf("%d",dmax+1);
}

void DFS(int x,int dist){
    d[x]=dist;
    dmax=max(dmax,d[x]);
    for (int i=0;i<G[x].size();i++){
        int y=G[x][i];
        if (!d[y]){
            DFS(y,dist+1);
        }
    }
}