57182023-09-09 19:52:55kukkermanElágazás nélküli úton levő települések (50 pont)cpp14Hibás válasz 31/5029ms6576 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ÖsszpontTesztVerdiktIdőMemória
base31/50
1Elfogadva0/03ms1808 KiB
2Elfogadva0/029ms4628 KiB
3Hibás válasz0/22ms2144 KiB
4Elfogadva2/22ms2236 KiB
5Elfogadva2/22ms2436 KiB
6Hibás válasz0/22ms2672 KiB
7Elfogadva2/23ms2768 KiB
8Elfogadva2/24ms3228 KiB
9Elfogadva2/26ms3656 KiB
10Elfogadva2/28ms3872 KiB
11Elfogadva2/214ms4556 KiB
12Elfogadva2/216ms4596 KiB
13Elfogadva3/34ms3736 KiB
14Hibás válasz0/34ms4020 KiB
15Hibás válasz0/36ms4164 KiB
16Hibás válasz0/36ms4376 KiB
17Hibás válasz0/314ms5016 KiB
18Hibás válasz0/314ms5208 KiB
19Elfogadva3/317ms5812 KiB
20Elfogadva3/328ms6544 KiB
21Elfogadva3/329ms6576 KiB
22Elfogadva3/329ms6576 KiB