Cod sursa(job #2055366)

Utilizator JiyuuNoTsubasaMaria Guran JiyuuNoTsubasa Data 3 noiembrie 2017 09:51:18
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#define N 100002
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");

int st[N], d[N];
struct nod{
    int nr;
    nod *urm;
};
nod *v[N];
void adaug(int x, int y){
    nod *p = new nod;
    p->nr = y;
    p->urm = v[x];
    v[x] = p;
}
void dfs(int ns, int n, int &far){
    int l = 1, Max = -1;
    bool found;
    st[l] = ns;
    d[ns] = 1;
    while(l){
        found = false;
        for(nod *p = v[st[l]];p && found == false;p = p->urm){
            if(d[p->nr] == 0){
                d[p->nr] = d[st[l]] + 1;
                st[++l] = p->nr;
                if(d[p->nr] > Max){
                    Max = d[p->nr];
                    far = p->nr;
                }
                found = true;
            }
        }
        if(found == false)
            l--;
    }
}
int main()
{
    int n, x, y, first = 1, last = 1;
    in>>n;
    for(int i=1;i<n;i++){
        in>>x>>y;
        adaug(x,y);
        adaug(y,x);
    }
    dfs(1,n,first);
    for(int i=1;i<=n;i++)
        st[i] = d[i] = 0;
    dfs(first,n,last);
    out<<d[last] - d[first] + 1<<"\n";
    return 0;
}