Cod sursa(job #1695071)

Utilizator razvandRazvan Dumitru razvand Data 26 aprilie 2016 15:31:05
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <bitset>
#include <queue>
#define MAX 100003

using namespace std;

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

vector<int> vec[MAX];
bitset<MAX> viz;
int level[MAX];
vector<int>::iterator it;

void bfs(int nod) {

    viz.reset();

    for(int i = 1; i <= MAX; i++)
        level[i] = 0;

    queue<int> que;
    que.push(nod);
    viz[nod] = 1;

    while(!que.empty()) {

        nod = que.front();
        que.pop();
        viz[nod] = 1;

        for(it = vec[nod].begin(); it != vec[nod].end(); it++) {

            if(!viz[*it]) {

                level[*it] = level[nod]+1;
                que.push(*it);

            }

        }

    }

}

int main() {

    int n,x,y;
    in >> n;

    for(int i = 1; i <= n; i++) {

        in >> x >> y;
        vec[x].push_back(y);
        vec[y].push_back(x);

    }

    bfs(1);
    int mx = 0;

    for(int i = 1; i <= n; i++) {
        if(level[i] > level[mx])
            mx = i;
    }

    bfs(mx);
    mx = 0;

    for(int i = 1; i <= n; i++) {
        if(level[mx] < level[i])
            mx = i;
    }

    out << level[mx]+1;

    return 0;
}