Pagini recente » Cod sursa (job #2184531) | Cod sursa (job #1806784) | Cod sursa (job #2951719) | Cod sursa (job #1952476) | Cod sursa (job #2206345)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
void read(int &n, vector<vector<int>> &G) {
ifstream fin("darb.in");
if (!fin.is_open()) {
cout << "The file can't be opened!\n";
exit(EXIT_FAILURE);
}
fin >> n;
G.resize(n + 1);
for (int i = 0; i < n - 1; ++i) {
int x, y;
fin >> x >> y;
G[x].emplace_back(y);
G[y].emplace_back(x);
}
fin.close();
}
void elimin(int n, const vector<vector<int>> &G) {
queue<int> Q;
vector<int> viz(n + 1, 0);
vector<int> d(n + 1, 0); //degree
for (int i = 1; i <= n; ++i) {
if (G[i].size() == 1) {
viz[i] = 1;
Q.push(i);
}
d[i] = G[i].size();
}
ofstream fout("darb.out");
if (n == 1) {
fout << 1 << '\n';
}
int r = 0, diam = 0;
while (n >= 3) {
int nrTerm = Q.size();
r += 1;
diam += 2;
for (int i = 1; i <= nrTerm; ++i) {
int u = Q.front();
n--;
d[u]--;
Q.pop(); //elimina nodul terminal u din coada
//Gaseste vecinul nodului u
int vec = 0;
for (auto v : G[u]) {
if (viz[v] == 0) {
vec = v;
break;
}
}
--d[vec];
if (d[vec] == 1) {
Q.push(vec);
viz[vec] = 1;
}
}
}
if (n == 1) {
fout << diam + 1<< '\n';
}
else if (n == 2) {
fout << diam + 2 << '\n';
}
}
int main() {
int n;
vector<vector<int>> G;
read(n, G);
elimin(n, G);
return 0;
}