5722 2023. 09. 09 22:20:07 kukkerman Elágazás nélküli úton levő települések (50 pont) cpp14 Futási hiba 31/50 29ms 64648 KiB
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#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;
}

void dfs(size_t elozo, size_t akt, const std::vector<std::vector<size_t>> &sz, std::set<size_t> &varosok) {
    if (sz[akt].size() > 1) {
        varosok.insert(akt);
    }

    if (sz[akt].size() <= 2) {
        dfs(akt, sz[akt][0] == elozo ? sz[akt][1] : sz[akt][0], sz, varosok);
    } 
}

void feldolgoz_dfs(const std::vector<std::vector<size_t>> &sz) {
    const auto n = sz.size();

    std::set<size_t> varosok;
    for (auto i = 0u; i < n; i++) {
        if (sz[i].size() == 1) {
            dfs(n, i, sz, varosok);
        }
    }

    std::cout << varosok.size() << std::endl;
    if (!varosok.empty()) {
        for (const auto v : varosok) {
            std::cout << v + 1 << ' ';
        }
        std::cout << std::endl;
    }
}

int main() {
    const auto sz = beolvas(std::cin);
    feldolgoz_dfs(sz);

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 31/50
1 Elfogadva 0/0 3ms 1812 KiB
2 Elfogadva 0/0 29ms 4560 KiB
3 Futási hiba 0/2 26ms 64648 KiB
4 Elfogadva 2/2 2ms 2444 KiB
5 Elfogadva 2/2 2ms 2540 KiB
6 Hibás válasz 0/2 3ms 2668 KiB
7 Elfogadva 2/2 2ms 2788 KiB
8 Elfogadva 2/2 4ms 3032 KiB
9 Elfogadva 2/2 6ms 3268 KiB
10 Elfogadva 2/2 8ms 3628 KiB
11 Elfogadva 2/2 14ms 4316 KiB
12 Elfogadva 2/2 16ms 4304 KiB
13 Elfogadva 3/3 4ms 3300 KiB
14 Hibás válasz 0/3 4ms 3548 KiB
15 Hibás válasz 0/3 6ms 3876 KiB
16 Futási hiba 0/3 6ms 4108 KiB
17 Hibás válasz 0/3 14ms 5032 KiB
18 Hibás válasz 0/3 14ms 5252 KiB
19 Elfogadva 3/3 17ms 5784 KiB
20 Elfogadva 3/3 28ms 6548 KiB
21 Elfogadva 3/3 28ms 6556 KiB
22 Elfogadva 3/3 28ms 6552 KiB