Cod sursa(job #2606723)

Utilizator CosminBanicaBanica Cosmin CosminBanica Data 28 aprilie 2020 12:58:09
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100009

class Task {
  public:
    void solve() {
        read_input();
        print_output(get_result());
    }

  private:
    int n;
    vector<int> adj[NMAX];

    void read_input() {
        ifstream fin("darb.in");
        fin >> n;

        for (int i = 1; i <= n - 1; ++i) {
            int x, y;
            fin >> x >> y;

            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        fin.close();
    }

    int get_result() {
        return do_bfs();
    }

    int do_bfs() {
        return bfs(1);
    }

    int bfs(int source) {
        queue<int> Q;
        vector<int> visited (n + 1, 0);

        Q.push(source);
        int last_visited;

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

            for (auto it : adj[node]) {
                if (!visited[it]) {
                    visited[it] = 1;
                    Q.push(it);
                }
            }

            last_visited = node;
        }

        visited = vector<int>(n + 1, 0);
        Q.push(last_visited);
        vector<int> d(n + 1);

        for (int i = 1; i <= n; ++i) {
            d[i] = INT_MAX;
        }

        d[last_visited] = 0;

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

            for (auto it : adj[node]) {
                if (d[node] + 1 < d[it]) {
                    d[it] = d[node] + 1;

                    Q.push(it);
                }
            }

            last_visited = node;
        }

        return d[last_visited] + 1;
    }

    void print_output(int sol) {
        ofstream fout("darb.out");
        
        fout << sol << "\n";

        fout.close();
    }
};

int main() {
    Task *task = new Task();
    task->solve();
    delete task;

    return 0;
}