Cod sursa(job #1166667)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 3 aprilie 2014 18:59:29
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
// Diametrul unui GRAF - O(N)

#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#define Nmax 100099
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");

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

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=G[node].begin(); it!=G[node].end(); ++it )
            if(!viz[*it])
            {
               viz[*it]=1 , last=*it;
               D=d[*it]=d[node]+1;
               Q.push(*it);
            }
    }
}


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