Cod sursa(job #1429441)

Utilizator MaarcellKurt Godel Maarcell Data 6 mai 2015 13:25:50
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int N,d[100010],l[100010]; vector<int> graf[100010]; bool v[100010];

void dfs(int nod){
    if (v[nod]) return;
    v[nod]=1;

    int i,max1=0,max2=0;
    for (i=0; i<graf[nod].size(); i++)
        dfs(graf[nod][i]);

    for (i=0; i<graf[nod].size(); i++)
        l[nod]=max(l[nod],l[graf[nod][i]]);
    l[nod]++;

    for (i=0; i<graf[nod].size(); i++)
        if (l[graf[nod][i]]>max1){
            max2=max1;
            max1=l[graf[nod][i]];
        }
        else if (l[graf[nod][i]]>max2){
            max2=l[graf[nod][i]];
        }

    d[nod]=max1+max2+1;
    for (i=0; i<graf[nod].size(); i++)
        d[nod]=max(d[nod],d[graf[nod][i]]);
}

int main(){
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin >> N;

    int i,x,y;
    for (i=1; i<N; i++){
        fin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    dfs(1);
    int MAX=0;
    for (i=1; i<=N; i++)
        MAX=max(MAX,d[i]);
    fout << MAX << "\n";

    return 0;
}