Pagini recente » Cod sursa (job #527314) | Cod sursa (job #1167428) | Cod sursa (job #1433119) | Cod sursa (job #1557983) | Cod sursa (job #2812838)
#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;
}