Cod sursa(job #1129908)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 28 februarie 2014 10:13:25
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
#define Nmax 100099
#define oo 2000000000
using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

int N,D,last,d[Nmax];
vector < int > G[Nmax];
queue < int > Q;

void  BFS(int S)
{
     for(int i=1;i<=N;++i)d[i]=oo;
     Q.push(S),d[S]=1;
     for( ;  !Q.empty() ; Q.pop())
     {
          int node = Q.front();
          for(vector < int > ::iterator it=G[node].begin();it!=G[node].end();++it)
               if(d[*it]==oo)
               {
                    last=*it;
                    d[*it]=d[node]+1;
                    D=max(D,d[*it]);
                    Q.push(*it);
               }
     }
}

int  main()
{
     f>>N;
     for(int i=1;i<N;++i)
     {
          int x,y;
          f>>x>>y;
          G[x].push_back(y);
          G[y].push_back(x);
     }
     BFS(1);
     BFS(last);
     g<<D<<'\n';
     f.close();g.close();
     return 0;
}