Cod sursa(job #1552851)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 18 decembrie 2015 20:13:20
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> g[100010];
int seen[100010],depth[100010],maxim=-1,which;
void dfs(int node){
    int i,dim=g[node].size();
    if(depth[node]>maxim){
        maxim=depth[node];
        which=node;
    }
    for(i=0;i<dim;i++)
        if(seen[g[node][i]]==0){
            depth[g[node][i]]=depth[node]+1;
            seen[g[node][i]]=1;
            dfs(g[node][i]);
        }
}
int main(){
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    int n,i,a,b;
    scanf("%d",&n);
    for(i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    depth[1]=1;
    seen[1]=1;
    dfs(1);
    memset(seen,0,sizeof(seen));
    depth[which]=1;
    seen[which]=1;
    dfs(which);
    printf("%d",maxim);
    return 0;
}