Cod sursa(job #2046750)

Utilizator DianaVelciovVelciov Diana DianaVelciov Data 24 octombrie 2017 08:56:55
Problema Diametrul unui arbore Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

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

const int N_MAX = 1e5 + 5;
int N, use[N_MAX], maxim;
vector <int> G[N_MAX];
queue <int> q;

void bfs(int node){
    use[node] = 1;
    q.push(node);
    while (!q.empty()){
        int a = q.front();
        q.pop();
        for (int vecin : G[a])
            if (!use[vecin]){
                use[vecin] = use[a] + 1;
                q.push(vecin);
            }
    }
}

void solve(int node){
    memset(use, 0, sizeof use);
    bfs(node);
    for (int i = 1; i <= N; ++i){
        if (maxim < use[i])
            maxim = use[i];
    }
}

int main(){
    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);
    }
    for (int i = 1; i <= N; ++i){
        if ((int)G[i].size() == 1)
            solve(i);
    }
    out << maxim;
    in.close(); out.close();
    return 0;
}