Cod sursa(job #1261840)

Utilizator rebound212Mihnea Savu rebound212 Data 12 noiembrie 2014 19:13:04
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<cstdio>
#include<vector>
#include <cstring>
#include <algorithm>
using namespace std;

int n,i,x,y,sol,d[100002],q[100002],last,diam;
bool sel[100002];
vector<int> g[100002];
void bfs(int nod)
{
    int p,u;
   memset(q,0,sizeof(q));
   memset(sel,false,sizeof(sel));
   p=u=1;
   d[nod]=1;
   sel[nod]=true;
   q[p]=nod;
   while(p<=u)
   {
       nod=q[p];
       for(vector<int> :: iterator it=g[nod].begin();it!=g[nod].end();it++)
       {
           if(!sel[*it])
           {
               sel[*it]=true;
               q[++u]=*it;
               d[*it]=d[nod]+1;
               diam=d[*it];
               last=*it;
           }
       }
       p++;
   }

}

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);

    }
   bfs(1);
   bfs(last);
   printf("%d",diam);
}