Cod sursa(job #1367736)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 2 martie 2015 02:29:14
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>

#define Nmax 100005
#define inf 0x3f3f3f3f

using namespace std;

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

vector<int> G[Nmax];
int D[Nmax];
int lastNode;

int BFS(int start)
{
    queue<int> Q;

    memset(D, inf, sizeof(D));
    D[start] = 1;

    Q.push(start);
    while (!Q.empty())
    {
        int node = Q.front();
        Q.pop();

        for (int i = 0; i < G[node].size(); i++)
        {
            int nextNode = G[node][i];

            if (D[node] + 1 < D[nextNode])
            {
                D[nextNode] = D[node] + 1;
                Q.push(nextNode);
            }
        lastNode = node;
        }
    }
    return D[lastNode];
}

int main()
{
    int n;
    in >> n;

    for (int i = 1; i < n; i++)
    {
        int x, y;
        in >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    BFS(1);
    out << BFS(lastNode) << "\n";
}