Cod sursa(job #1466717)

Utilizator CollermanAndrei Amariei Collerman Data 29 iulie 2015 23:47:13
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <bitset>
#include <queue>
#include <vector>
using namespace std;
ofstream fout("darb.out");
ifstream fin("darb.in");
const int NMAX = 100005;

int n, Max1, Max2;
int Niv[NMAX];
bitset<NMAX> Viz;
vector<int> Graf[NMAX];
queue<int> Q;

void bfs(int first)
{
    Viz[first] = true;
    Q.push(first);
    Niv[first] = 1;

    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();

        for(auto x : Graf[nod]) {
            if(!Viz[x]) {
                Q.push(x);
                Viz[x] = true;
                Niv[x] = Niv[nod] + 1;

                if(Niv[x] >= Max1) {
                    Max2 = Max1;
                    Max1 = Niv[x];
                }
            }
        }
    }
}

int main()
{
    fin >> n;
    for(int i=1, x, y; i<=n; i++) {
        fin >> x >> y;
        Graf[x].push_back(y);
        Graf[y].push_back(x);
    }

    bfs(1);
    fout << Max1 + Max2 - 1 << '\n';
    return 0;
}