Cod sursa(job #1251531)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 29 octombrie 2014 17:27:42
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <bitset>
#include <list>
#define DIM 100011
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int n,Dmax,Nmax;
int D[DIM];

list<int> L[DIM];
bitset<DIM> V,viz;

void dfs1(int nod,int d){
    list<int>::iterator it;
    V[nod]=1;
    if(Dmax<d)
        Dmax=d,Nmax=nod;
    for(it=L[nod].begin();it!=L[nod].end();it++)
        if(!V[*it])
            dfs1(*it,d+1);
}

void dfs2(int nod,int d){
    list<int>::iterator it;
    viz[nod]=1;
    if(Dmax<d)
        Dmax=d;
    for(it=L[nod].begin();it!=L[nod].end();it++)
        if(!viz[*it])
            dfs2(*it,d+1);
}

int main(void){
    register int i,j,x,y;

    f>>n;
    for(i=1;i<=n;i++) {
        f>>x>>y;
        L[x].push_front(y);
        L[y].push_front(x);
    }
    dfs1(1,0);
    V.reset();
    Dmax=0;
    dfs2(Nmax,0);
    g<<Dmax+1;
    f.close(),g.close();
    return 0;
}