Cod sursa(job #1848647)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 16 ianuarie 2017 13:12:53
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define NM 100005
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
int n,a,b,ultim,diametru,ii;
int viz[NM],dist[NM];
queue <int> q;
vector <int> v[NM];
int main()
{
    in>>n;
    for(int i=1;i<n;++i)
    {
        in>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dist[1]=1;
    viz[1]=1;
    q.push(1);
    while(!q.empty())
    {
        ii=q.front();
        q.pop();
        for(int i=0;i<v[ii].size();++i)
        {
            if(viz[v[ii][i]]==0)
            {
                q.push(v[ii][i]);
                viz[v[ii][i]]=1;
                dist[v[ii][i]]=dist[ii]+1;
                ultim=ii;
            }
        }
    }
    for(int i=0;i<=n;++i)
    {
        viz[i]=0;
        dist[i]=0;
    }
    dist[ultim]=1;
    viz[ultim]=1;
    q.push(ultim);
    while(!q.empty())
    {
        ii=q.front();
        q.pop();
        for(int i=0;i<v[ii].size();++i)
        {
            if(viz[v[ii][i]]==0)
            {
                q.push(v[ii][i]);
                viz[v[ii][i]]=1;
                dist[v[ii][i]]=dist[ii]+1;
                ultim=ii;
                diametru=dist[v[ii][i]];
            }
        }
    }
    out<<diametru+1;
    return 0;
}