Cod sursa(job #1517124)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 3 noiembrie 2015 21:29:12
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb

#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int n;

int visited[100001] = {0};
int length[100001] = {0};
vector<int> *arbore;

int bfs(int from,int value)
{
    int last = from;

    queue<int> q;
    q.push(from);
    visited[from] = value;
    length[from] = 0;
    while (q.empty() == 0)
    {
        int c = q.front();
        last = c;
        q.pop();
        for (int a = 0;a < arbore[c].size();a += 1)
        {
            if (visited[arbore[c].at(a)] != value)
            {
                q.push(arbore[c].at(a));
                length[arbore[c].at(a)] = length[c] + 1;
                visited[arbore[c].at(a)] = value;
            }
        }
    }
    return last;
}

int main(void)
{
    fstream fin("darb.in",ios::in);
    fstream fout("darb.out",ios::out);

    fin >> n;

    arbore = new vector<int>[100001];
    for (int a = 0;a < n - 1;a += 1)
    {
        int x;
        int y;
        fin >> x >> y;
        x -= 1;
        y -= 1;
        arbore[x].push_back(y);
        arbore[y].push_back(x);
    }

    fout << length[bfs(bfs(0,1),2)] + 1;

    fin.close();
    fout.close();

    return 0;
}