Cod sursa(job #2781360)

Utilizator andcovAndrei Covaci andcov Data 9 octombrie 2021 12:08:20
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
//
// Created by Andrei Covaci on 03.09.2021.
//

#include <fstream>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define INPUT "darb.in"
#define OUTPUT "darb.out"
//#define INPUT "input.in"
//#define OUTPUT "output.out"

vector<vector<int>> adj(100001, vector<int>());
vector<int> dist(100001);
bool vis1[100001];
bool vis2[100001];
int last;

int read() {
    ifstream in(INPUT);

    int a, b, n;

    in >> n;
    n--;

    for(; n; --n) {
        in >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    in.close();
    return 0;
}


void bfs1(int n) {
    queue<int> l;
    l.push(n);

    while(!l.empty()) {
        int curr = l.front();

        if(vis1[curr]) {
            continue;
        }

        vis1[curr] = true;
        last = curr;

        for(auto e : adj[curr]) {
            if (!vis1[e]) {
                l.push(e);
            }
        }

        l.pop();
    }
}

void bfs2(int n) {
    queue<int> l;
    l.push(n);
    dist[n] = 1;

    while(!l.empty()) {
        int curr = l.front();

        if(vis2[curr]) {
            continue;
        }

        vis2[curr] = true;
        last = curr;

        for(auto e : adj[curr]) {
            if (!vis2[e]) {
                l.push(e);
                dist[e] = dist[curr] + 1;
            }
        }

        l.pop();
    }
}

int solve(int _) {
    bfs1(1);
    bfs2(last);

    return dist[last];
}

void print(int res) {
    ofstream out(OUTPUT);

    out << res;

    out.close();
}

int main() {
    auto in = read();
    auto out = solve(in);
    print(out);

    return 0;
}