Pagini recente » Cod sursa (job #1558232) | Monitorul de evaluare | Cod sursa (job #694858) | Cod sursa (job #94512) | Cod sursa (job #1815882)
#include <algorithm>
#include <fstream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
struct Nod
{
int distanta;
vector<int> vecini;
};
using Arbore = vector<Nod>;
void AflaDistante(Arbore &arb)
{
vector<int> legaturi(arb.size(), 0);
vector<bool> vizitat(arb.size(), false);
queue<int> coada;
for (unsigned i = 0; i < arb.size(); ++i) {
legaturi[i] = arb[i].vecini.size();
if (legaturi[i] == 1)
coada.push(i);
arb[i].distanta = 0;
}
while (!coada.empty()) {
int nod = coada.front();
coada.pop();
vizitat[nod] = true;
for (int v : arb[nod].vecini) {
--legaturi[v];
if (!vizitat[v])
arb[v].distanta = max(arb[v].distanta, arb[nod].distanta + 1);
if (legaturi[v] == 1)
coada.push(v);
}
}
}
int AflaNodSalvare(const Arbore &arb, const set<int> &folosit)
{
vector<pair<int, int>> dist_noduri;
for (unsigned i = 1; i < arb.size(); ++i)
dist_noduri.push_back({arb[i].distanta, i});
sort(dist_noduri.begin(), dist_noduri.end(), greater<pair<int, int>>());
for (auto &p : dist_noduri)
if (folosit.find(p.second) == folosit.end())
return p.second;
return 0;
}
void Actualizeaza(Arbore &arb, int nod)
{
queue<int> coada;
coada.push(nod);
arb[nod].distanta = 0;
while (!coada.empty()) {
nod = coada.front();
coada.pop();
for (int v : arb[nod].vecini) {
if (arb[v].distanta > arb[nod].distanta + 1) {
arb[v].distanta = arb[nod].distanta + 1;
coada.push(v);
}
}
}
}
pair<int, set<int>> AflaSalvari(Arbore &arb, int k)
{
set<int> salvari;
AflaDistante(arb);
for (int i = 1; i <= k; ++i) {
int nod = AflaNodSalvare(arb, salvari);
salvari.insert(nod);
Actualizeaza(arb, nod);
}
int tmax = 0;
for (unsigned i = 1; i < arb.size(); ++i)
tmax = max(tmax, arb[i].distanta);
return {tmax + 1, salvari};
}
int main()
{
ifstream fin("salvare.in");
ofstream fout("salvare.out");
int n, k;
fin >> n >> k;
Arbore arbore(n + 1);
for (int i = 1; i < n; ++i) {
int x, y;
fin >> x >> y;
arbore[x].vecini.push_back(y);
arbore[y].vecini.push_back(x);
}
auto rez = AflaSalvari(arbore, k);
fout << rez.first << "\n";
for (int i : rez.second)
fout << i << " ";
return 0;
}