Cod sursa(job #2012273)

Utilizator workwork work work Data 18 august 2017 14:04:32
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

FILE *F=fopen("darb.in", "r"), *G=fopen("darb.out", "w");

int n, d[100005], l, m, x, y;
queue<int> q;
bitset<100005> v;
vector<int> a[100005];

void bfs(int nod)
{
    vector<int> :: iterator it;
    //for(int i = 1; i <= n; ++ i) d[i] = 0;
    v = 0;
    q.push(nod); v[nod] = 1; d[nod] = 1;
    while(!q.empty())
    {
        x = q.front(); q.pop();
        for(it = a[x].begin(); it != a[x].end(); ++ it)
            if(!v[*it])
                q.push(*it), v[*it] = 1, d[*it] = d[x] + 1;
    }
}

int main()
{
    fscanf(F, "%d ", &n);
    for(int i = 1; i <= n; ++ i)
    {
        fscanf(F, "%d %d ", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    bfs(1);
    for(int i = 2; i <= n; ++ i)
        if(l < d[i]) l = d[i], m = i;
    bfs(m); l = 0;
    for(int i = 1; i <= n; ++ i) l = max(l, d[i]);
    fprintf(G, "%d", l);
    return 0;
}