Cod sursa(job #1293772)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 16 decembrie 2014 15:53:18
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=100000;
bool vis[N+1];
vector<int>g[N+1];
int n;
int far,dist,mdist;
void dfs(int dad){
    vis[dad]=true;
    if(dist>mdist){
        mdist=dist;
        far=dad;
    }
    for(int i=0;i<g[dad].size();i++){
        int son=g[dad][i];
        if(!vis[son]){
            dist++;
            dfs(son);
            dist--;
        }
    }
}
int main(){
    freopen("diametru.in","r",stdin);
    freopen("diametru.out","w",stdout);
    scanf("%d",&n);
    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);
    }
    dfs(1); memset(vis,0,sizeof(vis));
    dfs(far);
    printf("%d",mdist+1);
    return 0;
}