Cod sursa(job #2812838)

Utilizator bianca_voicuBianca Voicu bianca_voicu Data 5 decembrie 2021 12:05:57
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int INF = 1 << 30;

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

class Graph {
private:
    int _n, _m;
    vector<vector<int>> _adjacentList; // liste de adiacenta

    vector<vector<pair<int, int> >> _adjacentListWithCosts;

    int viz[100001] = {0};
public:
    void setAdjacentList(const vector<vector<int>> &adjacentList);

public:
    Graph(int nodes, int edges) : _n(nodes), _m(edges) {}

    void addEdges();

    void dfsDarb(int start, vector<int> &level, int l);

    int darb();
};

void Graph::addEdges() {
    int x, y, i;
    for (i = 0; i < _m; i++) {
        f >> x >> y;
        _adjacentList[x].push_back(y);
        _adjacentList[y].push_back(x);
    }
}


void Graph::dfsDarb(int node, vector<int> &level, int l) {
    viz[node] = 1;
    level[node] = l;
    for (int i = 0; i < _adjacentList[node].size(); ++i) {
        if (!viz[_adjacentList[node][i]]) {
            dfsDarb(_adjacentList[node][i], level, l + 1);
        }
    }
}

int Graph::darb() {
    int diameter = 0;
    vector<int> level(_n + 1, 0);
    int maxLevel = 0;
    int finale = 0;

    dfsDarb(1, level, 0);

    for (int i = 0; i < _n; ++i)
        if (level[i] > maxLevel) {
            maxLevel = level[i];
            finale = i;
        }

    for (int i = 0; i <= _n; ++i) {
        viz[i] = 0;
    }
    level.clear();
    dfsDarb(finale, level, 0);

    for (int i = 0; i <= _n; ++i)
        if (level[i] > diameter)
            diameter = level[i];

    return diameter + 1;
}

void Graph::setAdjacentList(const vector<vector<int>> &adjacentList) {
    _adjacentList = adjacentList;
}


int main() {
    int n, x, y;
    f >> n;
    Graph grf(n, n - 1);
    vector<vector<int>> gr(100001);

    for (int i = 0; i < n - 1; ++i) {
        f >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    grf.setAdjacentList(gr);

    g << grf.darb();

    f.close();
    g.close();
    return 0;
}