5718 | 2023. 09. 09 19:52:55 | kukkerman | Elágazás nélküli úton levő települések (50 pont) | cpp14 | Hibás válasz 31/50 | 29ms | 6576 KiB |
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
std::vector<std::vector<size_t>> beolvas(std::istream &in) {
size_t t, u;
in >> t >> u;
std::vector<std::vector<size_t>> sz(t);
for (auto i = 0u; i < u; i++) {
size_t honnan, hova;
in >> honnan >> hova;
honnan--;
hova--;
sz[honnan].push_back(hova);
sz[hova].push_back(honnan);
}
return sz;
}
void feldolgoz(const std::vector<std::vector<size_t>> &sz) {
const auto n = sz.size();
std::deque<size_t> q;
for (auto i = 0u; i < n; i++) {
if (sz[i].size() == 1) {
q.push_back(i);
}
}
std::vector<size_t> varosok;
std::vector<bool> lattam(n, false);
while (!q.empty()) {
const auto v = q.front();
q.pop_front();
if (!lattam[v]) {
lattam[v] = true;
if (sz[v].size() != 1) {
varosok.push_back(v);
}
if (sz[v].size() <= 2) {
for (const auto u : sz[v]) {
q.push_back(u);
}
}
}
}
std::sort(varosok.begin(), varosok.end());
std::cout << varosok.size() << std::endl;
for (const auto v : varosok) {
std::cout << v + 1 << ' ';
}
std::cout << std::endl;
}
int main() {
const auto sz = beolvas(std::cin);
feldolgoz(sz);
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 31/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1808 KiB | |||
2 | Elfogadva | 0/0 | 29ms | 4628 KiB | |||
3 | Hibás válasz | 0/2 | 2ms | 2144 KiB | |||
4 | Elfogadva | 2/2 | 2ms | 2236 KiB | |||
5 | Elfogadva | 2/2 | 2ms | 2436 KiB | |||
6 | Hibás válasz | 0/2 | 2ms | 2672 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 2768 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3228 KiB | |||
9 | Elfogadva | 2/2 | 6ms | 3656 KiB | |||
10 | Elfogadva | 2/2 | 8ms | 3872 KiB | |||
11 | Elfogadva | 2/2 | 14ms | 4556 KiB | |||
12 | Elfogadva | 2/2 | 16ms | 4596 KiB | |||
13 | Elfogadva | 3/3 | 4ms | 3736 KiB | |||
14 | Hibás válasz | 0/3 | 4ms | 4020 KiB | |||
15 | Hibás válasz | 0/3 | 6ms | 4164 KiB | |||
16 | Hibás válasz | 0/3 | 6ms | 4376 KiB | |||
17 | Hibás válasz | 0/3 | 14ms | 5016 KiB | |||
18 | Hibás válasz | 0/3 | 14ms | 5208 KiB | |||
19 | Elfogadva | 3/3 | 17ms | 5812 KiB | |||
20 | Elfogadva | 3/3 | 28ms | 6544 KiB | |||
21 | Elfogadva | 3/3 | 29ms | 6576 KiB | |||
22 | Elfogadva | 3/3 | 29ms | 6576 KiB |