Cod sursa(job #1476689)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 25 august 2015 12:43:42
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <deque>

using namespace std;

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

const int NMax = 1e5 + 5;

int sol, last;
int D[NMax];
bool viz[NMax];

deque < int > que;
vector < int > G[NMax];

void bfs(){
    int node;
    memset(viz, 0, sizeof(viz));
    memset(D, 0, sizeof(D));
    viz[que.front()] = 1;
    while(!que.empty()){
        node = que.front();
        last = node;
        que.pop_front();
        for(int i = 0; i < G[node].size(); i++){
            if(!viz[G[node][i]]){
                viz[G[node][i]] = 1;
                D[G[node][i]] = D[node] + 1;
                sol = D[G[node][i]];
                que.push_back(G[node][i]);
            }
        }
    }
}

int main(){
    int n, a, b;
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    que.push_back(1);
    bfs();
    que.push_back(last);
    bfs();
    fout << sol + 1;
    return 0;
}