5729 2023. 09. 10 16:05:04 kukkerman Elágazás nélküli úton levő települések (50 pont) cpp14 Elfogadva 50/50 29ms 6760 KiB
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

std::vector<std::vector<int>> beolvas(std::istream &in) {
    int t, u;
    in >> t >> u;

    std::vector<std::vector<int>> sz(t);
    for (auto i = 0; i < u; i++) {
        int honnan, hova;
        in >> honnan >> hova;
        honnan--;
        hova--;

        sz[honnan].push_back(hova);
        sz[hova].push_back(honnan);
    }

    return sz;
}

void dfs(int elozo, int akt, const std::vector<std::vector<int>> &sz, std::set<int> &varosok) {
    if (elozo != -1) {
        varosok.insert(akt);
    }

    const auto fokszam = sz[akt].size();
    if (fokszam == 1 && elozo == -1) {
        dfs(akt, sz[akt][0], sz, varosok);

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

void feldolgoz(const std::vector<std::vector<int>> &sz) {
    const auto n = static_cast<int>(sz.size());

    std::set<int> varosok;
    for (auto i = 0; i < n; i++) {
        if (sz[i].size() == 1) {
            dfs(-1, 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(sz);

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1964 KiB
2 Elfogadva 0/0 28ms 3976 KiB
3 Elfogadva 2/2 2ms 2320 KiB
4 Elfogadva 2/2 2ms 2532 KiB
5 Elfogadva 2/2 3ms 2776 KiB
6 Elfogadva 2/2 2ms 2840 KiB
7 Elfogadva 2/2 3ms 3088 KiB
8 Elfogadva 2/2 4ms 3192 KiB
9 Elfogadva 2/2 6ms 3528 KiB
10 Elfogadva 2/2 8ms 3968 KiB
11 Elfogadva 2/2 16ms 4608 KiB
12 Elfogadva 2/2 16ms 4588 KiB
13 Elfogadva 3/3 4ms 4044 KiB
14 Elfogadva 3/3 4ms 4336 KiB
15 Elfogadva 3/3 6ms 4628 KiB
16 Elfogadva 3/3 7ms 5104 KiB
17 Elfogadva 3/3 14ms 5180 KiB
18 Elfogadva 3/3 14ms 5600 KiB
19 Elfogadva 3/3 17ms 6156 KiB
20 Elfogadva 3/3 28ms 6440 KiB
21 Elfogadva 3/3 28ms 6760 KiB
22 Elfogadva 3/3 29ms 6756 KiB