Cod sursa(job #1152666)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 24 martie 2014 21:23:45
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>

using namespace std;

vector<int> l[100005];

int n,i,c[100005],d[100005],x,y,u,p,prim;

bool ok[100005];

int main() {
    ifstream f("darb.in");
    ofstream g("darb.out");
    f>>n;
    for(i=1;i<n;i++) {
        f>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    u=p=1;
    c[1]=ok[1]=1;
    while(p<=u) {
        for(i=0;i<l[c[p]].size();i++)
            if(ok[l[c[p]][i]]==0) {
                u++;
                c[u]=l[c[p]][i];
                ok[l[c[p]][i]]=1;
            }
        p++;
    }
    prim=c[u];
    p=u=1;
    for(i=1;i<=n;i++)
        ok[i]=0;
    c[1]=prim;
    d[1]=1;
    ok[prim]=1;
    while(p<=u) {
        for(i=0;i<l[c[p]].size();i++)
            if(ok[l[c[p]][i]]==0) {
                u++;
                c[u]=l[c[p]][i];
                d[u]=d[p]+1;
                ok[l[c[p]][i]]=1;
            }
        p++;
    }
    g<<d[u]<<"\n";
    return 0;
}