Cod sursa(job #2422345)

Utilizator test666014test test test666014 Data 18 mai 2019 13:56:53
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <memory>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <functional>
using namespace std;

class Tree {
public:
    Tree(int n, const vector<pair<int,int>>& edges) {
        this->n = n;
        this->e = vector<vector<int>>(n + 1);
        for (auto p : edges) {
            int x = p.first;
            int y = p.second;
            e[x].push_back(y);
            e[y].push_back(x);
        }
    }

    int CalculateDiameter() {
        int x = TheFarestNode(CalculateDistances(1));
        vector<int> dist = CalculateDistances(x);
        int y = TheFarestNode(dist);
        return dist[y] + 1;
    }

private:
    vector<int> CalculateDistances(int x) {
        vector<int> dist(n + 1, 0);
        vector<bool> viz(n + 1, 0);
        Dfs(x, viz, dist);
        return dist;
    }

    void Dfs(int x, vector<bool>& viz, vector<int>& dist) {
        viz[x] = true;
        for (auto y : e[x]) {
            if (!viz[y]) {
                dist[y] = dist[x] + 1;
                Dfs(y, viz, dist);
            }
        }
    }

    int TheFarestNode(const vector<int>& dist) {
        int best = 1;
        for (int i = 1; i <= n; ++i) {
            if (dist[i] > dist[best]) best = i;
        }
        return best;
    }

    int n;
    vector<vector<int>> e;
};

class Solution {
public:
    int TreeDiameter(int n, const vector<pair<int,int>>& edges) {
        Tree tree(n, edges);
        return tree.CalculateDiameter();
    }
};

int main() {
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "r", stdin);
    int n, x, y;
    vector<pair<int,int>> edges;
    scanf("%d", &n);
    for (int i = 0; i < n - 1; ++i) {
        scanf("%d %d", &x, &y);
        edges.emplace_back(x,y);
    }
    Solution s;
    printf("%d\n", s.TreeDiameter(n, edges));
    return 0;
}