Cod sursa(job #1094373)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 29 ianuarie 2014 13:05:45
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#define Nmax 100099
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");

int N,last,D,d[Nmax];
vector < int > Arb[Nmax];
bitset < Nmax > viz;
queue  < int > Q;

inline void ReadInput()
{
    f>>N;
    for(int i=1;i<N;++i)
    {
        int x,y;
        f>>x>>y;
        Arb[x].push_back(y);
        Arb[y].push_back(x);
    }
}

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

}

int main()
{
    ReadInput();
    BFS(1);
    BFS(last);
    g<<D<<'\n';
    return 0;
}