Cod sursa(job #1261500)

Utilizator rebound212Mihnea Savu rebound212 Data 12 noiembrie 2014 14:01:16
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <cstdio>
#include <climits>

#define PII pair < int , int >
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define LL long long
#define NMAX 20
using namespace std;
int sol[10001],x,y,nivel,n,dist,q[100001],p,u;
bool ok[100001];
vector <int> g[100001];

void bfs(int nod)
{  memset(ok,false,sizeof(ok));
  memset(q,0,sizeof(q));
     p=u=1;
     q[p]=nod;
    while(p<=u)
    {
        nod=q[p];
       ok[nod]=true;
       bool ok2=true;
        for(vector <int> :: iterator it=g[nod].begin(); it!=g[nod].end();it++)
        {
            if(!ok[*it]){q[++u]=*it; ok2=false;}
        }
        if(!ok2) nivel++;
        p++;
    }
}
int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&n);
    int i;


    for(i=1;i<n;i++)

    {
        scanf("%d %d",&x,&y);
        g[x].PB(y);
    }
    for(vector <int> :: iterator it=g[1].begin(); it!=g[1].end();it++)
    {   nivel=1;
    int r=*it;
        bfs(r);
        sol[++sol[0]]=nivel;
    }

sort(sol+1,sol+sol[0]+1);

printf("%d",sol[sol[0]]+sol[sol[0]-1]+1);

    return 0;
}