Cod sursa(job #1096894)

Utilizator vyrtusRadu Criuleni vyrtus Data 2 februarie 2014 18:25:00
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <deque>

#define nmax 100001
using namespace std;

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

vector <int> drum[nmax];
deque <pair<int,int> > coada;
int a[nmax];
int n,last,m = 0, sol = 0 ;

void bfs(int start,int k)
{
    coada.push_back(make_pair(start,k));
    a[start] = 1;
     while (!coada.empty())
     {
        int nod = coada.front().first , val = coada.front().second;
         for (int i=0;i<drum[nod].size();i++)
         {
             if (a[drum[nod][i]] == 0)
             {
                coada.push_back(make_pair(drum[nod][i],val+1));
                a[drum[nod][i]] = 1;
                if (val+1>m) { m = val+1; last = drum[nod][i]; }
             }
         }
     coada.pop_front();
    }
}

void dfs(int nod,int k)
{
    a[nod] = 0;
    if (k > sol) sol = k;
    for (int i=0;i<drum[nod].size();i++)
    {
       if (a[drum[nod][i]] == 1)  dfs(drum[nod][i],k+1);
    }
}

int main()
{
    f >> n;
    for (int i=0;i<n-1;i++)
    {
        int x,y;
         f >> x >>y;
         drum[x].push_back(y);
         drum[y].push_back(x);
    }

    bfs(1,0);
    dfs(last,1);
        g << sol ;

    return 0;
}