Cod sursa(job #1236031)

Utilizator japjappedulapPotra Vlad japjappedulap Data 1 octombrie 2014 10:43:03
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

ifstream is ("darb.in");
ofstream os ("darb.out");

int N, x, y, K, D[100002];
vector <int> V[100002];

int BFS(int k);

int main()
{
    is >> N;
    for (int i = 1; i < N; ++i)
    {
        is >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    memset(D, 0x3f3f3f3f, sizeof(D));
    K = BFS(1);
    memset(D, 0x3f3f3f3f, sizeof(D));
    os << D[BFS(K)]+1;


    is.close();
    os.close();
}

int BFS(int k)
{
    queue <int> Q;
    int i, mx = 0, pos;
    D[k] = 0;
    for (Q.push(k); !Q.empty(); Q.pop())
    {
        i = Q.front();
        for (int j = 0; j < V[i].size(); ++j)
        {
            if (D[V[i][j]] > D[i]+1)
            {
                D[V[i][j]] = D[i]+1;
                Q.push(V[i][j]);
                if (D[V[i][j]] > mx) mx = D[V[i][j]], pos = V[i][j];
            }
        }
    }
    return pos;
};