Cod sursa(job #1339751)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 11 februarie 2015 09:25:54
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>
#include <queue>
#include <vector>
const int maxn = 200 * 1000 + 5;
const int INF = 2 * 1000 * 1000;
int max(int a,int b)
{
    if(a<b) return b;
    return a;
}
int n, m, i, j, a, b, diametru, d[maxn], ans, t;
std::vector<int> G[maxn];
std::queue <int> Q;
 
void BFS(int sursa)
{
 
    Q.push(sursa);
    for(int i = 1; i <= n; ++i) d[i] = INF;
    d[sursa] = 0;
    while(!Q.empty())
    {
        int act = Q.front();
        Q.pop();
        for(int i = 0; i < G[act].size(); ++i)
        {
            int vecin = G[act][i];
            if(d[vecin] == INF)
            {
                d[vecin] = d[act] + 1;
                Q.push(vecin);
                diametru = max(diametru, d[vecin]);
            }
        }
    }
}
 
int main()
{
 
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
        scanf("%d",&n);
	m=n-1;
        diametru = 0;
        for(i = 1; i <= n; ++i) G[i].clear();
        for(i = 1; i <= m; ++i)
        {
            scanf("%d %d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        BFS(1);
        for(ans = 0; (1 << ans) < diametru; ++ans);
        printf("%d\n",ans);
    return 0;
}