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