Cod sursa(job #2196595)

Utilizator pakistanezuPopescu Alexandru Gabriel pakistanezu Data 19 aprilie 2018 19:42:20
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <vector>
#include <fstream>

// sursa veche

#define NMAX 100010
std::ifstream f("darb.in");
std::ofstream g("darb.out");

class Task {
public:
    void solve() {
        read_input();
        g << get_result();
    }
private:
    int n, m, maxNode = 0, maxCount = 0;
    std::vector<int> adj[NMAX];

    void read_input() {
        f >> n;
        m = n - 1;
        int x, y;
        for (int i = 1; i <= m; ++i) {
            f >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
    }

    int get_result() {
        int count = 0;
        std::vector<int> visited(n + 1, 0);
        dfs(1, visited, count);
        maxCount = count = 0;
        std::vector<int> visited2(n + 1, 0);
        dfs(maxNode, visited2, count);
        return maxCount;
    }

    void dfs(int node, std::vector<int> &visited, int &count) {
        ++count;
        visited[node] = true;
        if (count > maxCount) {
            maxNode = node;
            maxCount = count;
        }
        for (auto &v : adj[node]) {
            if (!visited[v]) {
                dfs(v, visited, count);
            }
        }
        --count;
    }
};
int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}